#include<iostream>
#include<cstdio>
using namespace std;

int tot=0,h[200005];
int n,cnt=0,S,T,del,scc[200005];
int fa[200005],val[200005];
struct Edge{
	int x,next;
}e[200005];
bool vis[200005];

inline void add_edge(int x,int y){
	e[++tot].x=y;
	e[tot].next=h[x],h[x]=tot;
}

inline int get_mex(int x){
	int ans;
	for(int i=h[x];i;i=e[i].next)if(del!=i)vis[val[e[i].x]]=1;
	for(int i=0;;i++)if(!vis[i]){ans=i;break;}
	for(int i=h[x];i;i=e[i].next)if(del!=i)vis[val[e[i].x]]=0;
	return ans;
}

void dfs(int x){
	scc[x]=cnt;
	for(int i=h[x];i;i=e[i].next)
		if(scc[e[i].x]){
			if(scc[e[i].x]==cnt)S=x,T=e[i].x,del=i;
		}else dfs(e[i].x);
	val[x]=get_mex(x);
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",fa+i);
		add_edge(fa[i],i);
	}
	for(int i=1;i<=n;i++)
		if(!scc[i])cnt++,dfs(i);
	if(S==0&&T==0)return puts("POSSIBLE"),0;
	int tmp1=get_mex(S);
	vis[tmp1]=true;
	int tmp2=get_mex(S);
	vis[tmp1]=false;
	if(val[T]!=tmp1)return puts("POSSIBLE"),0;
	val[S]=tmp2;
	for(int i=fa[S];i!=T;i=fa[i])val[i]=get_mex(i);
	if(get_mex(T)==tmp1)puts("POSSIBLE");
	else puts("IMPOSSIBLE");
}
### Prompt

Develop a solution in Cpp to the problem described below:

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>
using namespace std;

int tot=0,h[200005];
int n,cnt=0,S,T,del,scc[200005];
int fa[200005],val[200005];
struct Edge{
	int x,next;
}e[200005];
bool vis[200005];

inline void add_edge(int x,int y){
	e[++tot].x=y;
	e[tot].next=h[x],h[x]=tot;
}

inline int get_mex(int x){
	int ans;
	for(int i=h[x];i;i=e[i].next)if(del!=i)vis[val[e[i].x]]=1;
	for(int i=0;;i++)if(!vis[i]){ans=i;break;}
	for(int i=h[x];i;i=e[i].next)if(del!=i)vis[val[e[i].x]]=0;
	return ans;
}

void dfs(int x){
	scc[x]=cnt;
	for(int i=h[x];i;i=e[i].next)
		if(scc[e[i].x]){
			if(scc[e[i].x]==cnt)S=x,T=e[i].x,del=i;
		}else dfs(e[i].x);
	val[x]=get_mex(x);
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",fa+i);
		add_edge(fa[i],i);
	}
	for(int i=1;i<=n;i++)
		if(!scc[i])cnt++,dfs(i);
	if(S==0&&T==0)return puts("POSSIBLE"),0;
	int tmp1=get_mex(S);
	vis[tmp1]=true;
	int tmp2=get_mex(S);
	vis[tmp1]=false;
	if(val[T]!=tmp1)return puts("POSSIBLE"),0;
	val[S]=tmp2;
	for(int i=fa[S];i!=T;i=fa[i])val[i]=get_mex(i);
	if(get_mex(T)==tmp1)puts("POSSIBLE");
	else puts("IMPOSSIBLE");
}
```