#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <cstring>
#define N 200005

using namespace std;

struct edge{
	int to, nxt;
}e[N << 1];

int n, cnt, num, tot;
int a[N], p[N], fir[N], dfn[N], low[N], co[N];

stack < int > st;
vector < int > G[N];

void add(int ,int);
void Tarjan(int);
void dfs(int ,int);

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%d",p + i), add(p[i], i);
	for(int i = 1; i <= n; ++i)
		if(!dfn[i]) Tarjan(i);
	bool flag = true;
	for(int i = 1; i <= tot; ++i){
		int sz = G[i].size();
		if(sz == 1 || sz % 2 == 0) continue;
		for(int j = 0; j < sz; ++j)
			dfs(G[i][j], co[G[i][j]]);
		bool book = true;
		for(int j = 1; j < sz; ++j)
			if(a[G[i][j]] != a[G[i][j - 1]]){
				book = false;break;
			}
		if(book) flag = false;
	}
	if(flag) puts("POSSIBLE");
	else puts("IMPOSSIBLE");
	return 0;
}

void add(int u,int v){
	e[++cnt].to = v;e[cnt].nxt = fir[u];fir[u] = cnt;
	return ;
}

void Tarjan(int u){
	dfn[u] = low[u] = ++num;
	st.push(u);
	for(int i = fir[u]; i; i = e[i].nxt){
		int v = e[i].to;
		if(!dfn[v]) Tarjan(v), low[u] = min(low[u], low[v]);
		else if(!co[v]) low[u] = min(low[u], dfn[v]);
	}
	if(low[u] == dfn[u]){
		co[u] = ++tot;G[tot].push_back(u);
		while(st.top() != u){
			co[st.top()] = tot;
			G[tot].push_back(st.top());
			st.pop();
		}
		st.pop();
	}
	return ;
}

void dfs(int u,int x){
	bool vis[100];memset(vis, false, sizeof vis);
	for(int i = fir[u]; i; i = e[i].nxt){
		int v = e[i].to;
		if(co[v] == x) continue;
		dfs(v, x);vis[a[v]] = true;
	}
	int pos = 0;
	while(vis[pos]) ++pos;
	a[u] = pos;
	return ;
}

### Prompt

Construct a cpp code solution to the problem outlined:

There is a directed graph with N vertices and N edges. The vertices are numbered 1, 2, ..., N.

The graph has the following N edges: (p_1, 1), (p_2, 2), ..., (p_N, N), and the graph is weakly connected. Here, an edge from Vertex u to Vertex v is denoted by (u, v), and a weakly connected graph is a graph which would be connected if each edge was bidirectional.

We would like to assign a value to each of the vertices in this graph so that the following conditions are satisfied. Here, a_i is the value assigned to Vertex i.

* Each a_i is a non-negative integer.
* For each edge (i, j), a_i \neq a_j holds.
* For each i and each integer x(0 ≤ x < a_i), there exists a vertex j such that the edge (i, j) exists and x = a_j holds.



Determine whether there exists such an assignment.

Constraints

* 2 ≤ N ≤ 200 000
* 1 ≤ p_i ≤ N
* p_i \neq i
* The graph is weakly connected.

Input

Input is given from Standard Input in the following format:


N
p_1 p_2 ... p_N


Output

If the assignment is possible, print `POSSIBLE`; otherwise, print `IMPOSSIBLE`.

Examples

Input

4
2 3 4 1


Output

POSSIBLE


Input

3
2 3 1


Output

IMPOSSIBLE


Input

4
2 3 1 1


Output

POSSIBLE


Input

6
4 5 6 5 6 4


Output

IMPOSSIBLE

### Response

```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <cstring>
#define N 200005

using namespace std;

struct edge{
	int to, nxt;
}e[N << 1];

int n, cnt, num, tot;
int a[N], p[N], fir[N], dfn[N], low[N], co[N];

stack < int > st;
vector < int > G[N];

void add(int ,int);
void Tarjan(int);
void dfs(int ,int);

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%d",p + i), add(p[i], i);
	for(int i = 1; i <= n; ++i)
		if(!dfn[i]) Tarjan(i);
	bool flag = true;
	for(int i = 1; i <= tot; ++i){
		int sz = G[i].size();
		if(sz == 1 || sz % 2 == 0) continue;
		for(int j = 0; j < sz; ++j)
			dfs(G[i][j], co[G[i][j]]);
		bool book = true;
		for(int j = 1; j < sz; ++j)
			if(a[G[i][j]] != a[G[i][j - 1]]){
				book = false;break;
			}
		if(book) flag = false;
	}
	if(flag) puts("POSSIBLE");
	else puts("IMPOSSIBLE");
	return 0;
}

void add(int u,int v){
	e[++cnt].to = v;e[cnt].nxt = fir[u];fir[u] = cnt;
	return ;
}

void Tarjan(int u){
	dfn[u] = low[u] = ++num;
	st.push(u);
	for(int i = fir[u]; i; i = e[i].nxt){
		int v = e[i].to;
		if(!dfn[v]) Tarjan(v), low[u] = min(low[u], low[v]);
		else if(!co[v]) low[u] = min(low[u], dfn[v]);
	}
	if(low[u] == dfn[u]){
		co[u] = ++tot;G[tot].push_back(u);
		while(st.top() != u){
			co[st.top()] = tot;
			G[tot].push_back(st.top());
			st.pop();
		}
		st.pop();
	}
	return ;
}

void dfs(int u,int x){
	bool vis[100];memset(vis, false, sizeof vis);
	for(int i = fir[u]; i; i = e[i].nxt){
		int v = e[i].to;
		if(co[v] == x) continue;
		dfs(v, x);vis[a[v]] = true;
	}
	int pos = 0;
	while(vis[pos]) ++pos;
	a[u] = pos;
	return ;
}

```