#include <cstdio>
using namespace std;
const int N=200005;
int n,pre[N],cnex[N];
int h[N],tot;
struct Edge{
	int v,next;
}e[N*2];
int a[N],len,mex[N][2];
inline void addEdge(int u,int v){
	e[++tot]=(Edge){v,h[u]}; h[u]=tot;
}
void readData(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&pre[i]);
		addEdge(pre[i],i); 
	}
}
void findCircle(int u){
	static int stk[N],top=0;
	static bool vis[N];
	stk[++top]=u;
	vis[u]=true;
	if(vis[pre[u]]){
		int v=pre[u];
		cnex[v]=u;
		for(;stk[top]!=v;top--){
			cnex[stk[top]]=stk[top-1];
			a[++len]=stk[top];
		}
		a[++len]=v;
		return;
	}
	findCircle(pre[u]);
}
void dfs(int u,int dep){
	for(int i=h[u],v;i;i=e[i].next)
		if((v=e[i].v)!=cnex[u])
			dfs(v,dep+1);
	static int cnt[N];
	for(int i=h[u],v;i;i=e[i].next)
		if((v=e[i].v)!=cnex[u])
			cnt[mex[v][0]]++;
	for(mex[u][0]=0;cnt[mex[u][0]];mex[u][0]++);
	if(dep==0)
		for(mex[u][1]=mex[u][0]+1;cnt[mex[u][1]];mex[u][1]++);
	for(int i=h[u],v;i;i=e[i].next)
		if((v=e[i].v)!=cnex[u])
			cnt[mex[v][0]]--;
}
bool run(int x){
	int last=x;
	for(int i=len-1;i>=1;i--){
		int u=a[i];
		last=(mex[u][0]==last)?mex[u][1]:mex[u][0];
	}
	last=(mex[a[len]][0]==last)?mex[a[len]][1]:mex[a[len]][0];
	return x==last;
}
bool judge(){
	for(int i=1;i<=len;i++)
		dfs(a[i],0);
	return run(mex[a[len]][0])||run(mex[a[len]][1]);
}
int main(){
	readData();
	findCircle(1);
	puts(judge()?"POSSIBLE":"IMPOSSIBLE");
	return 0;
}
### Prompt

Create a solution in Cpp for the following problem:

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 <cstdio>
using namespace std;
const int N=200005;
int n,pre[N],cnex[N];
int h[N],tot;
struct Edge{
	int v,next;
}e[N*2];
int a[N],len,mex[N][2];
inline void addEdge(int u,int v){
	e[++tot]=(Edge){v,h[u]}; h[u]=tot;
}
void readData(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&pre[i]);
		addEdge(pre[i],i); 
	}
}
void findCircle(int u){
	static int stk[N],top=0;
	static bool vis[N];
	stk[++top]=u;
	vis[u]=true;
	if(vis[pre[u]]){
		int v=pre[u];
		cnex[v]=u;
		for(;stk[top]!=v;top--){
			cnex[stk[top]]=stk[top-1];
			a[++len]=stk[top];
		}
		a[++len]=v;
		return;
	}
	findCircle(pre[u]);
}
void dfs(int u,int dep){
	for(int i=h[u],v;i;i=e[i].next)
		if((v=e[i].v)!=cnex[u])
			dfs(v,dep+1);
	static int cnt[N];
	for(int i=h[u],v;i;i=e[i].next)
		if((v=e[i].v)!=cnex[u])
			cnt[mex[v][0]]++;
	for(mex[u][0]=0;cnt[mex[u][0]];mex[u][0]++);
	if(dep==0)
		for(mex[u][1]=mex[u][0]+1;cnt[mex[u][1]];mex[u][1]++);
	for(int i=h[u],v;i;i=e[i].next)
		if((v=e[i].v)!=cnex[u])
			cnt[mex[v][0]]--;
}
bool run(int x){
	int last=x;
	for(int i=len-1;i>=1;i--){
		int u=a[i];
		last=(mex[u][0]==last)?mex[u][1]:mex[u][0];
	}
	last=(mex[a[len]][0]==last)?mex[a[len]][1]:mex[a[len]][0];
	return x==last;
}
bool judge(){
	for(int i=1;i<=len;i++)
		dfs(a[i],0);
	return run(mex[a[len]][0])||run(mex[a[len]][1]);
}
int main(){
	readData();
	findCircle(1);
	puts(judge()?"POSSIBLE":"IMPOSSIBLE");
	return 0;
}
```