#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
using namespace std;
#define N 200005
int n,fa[N],cnt,head[N],vis[N],mk[N],f[N],len;
struct edge{int to,nxt;}e[N];
void adde(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
/*void dfs(int u){
	for (int i=head[u];i;i=e[i].nxt) if (!mk[e[i].to]){
		dfs(e[i].to);
		vis[f[e[i].to]]=1;
	}
	int mex=0;while (vis[mex]) mex++;f[u]=mex;
	for (int i=head[u];i;i=e[i].nxt) if (!mk[e[i].to]) vis[f[e[i].to]]=0;
}*/

void dfs(int u){
    for(int tmp=head[u];tmp;tmp=e[tmp].nxt){
        int v=e[tmp].to;
        if(!mk[v])dfs(v);
    }
    for(int tmp=head[u];tmp;tmp=e[tmp].nxt){
        int v=e[tmp].to;
        if(!mk[v])vis[f[v]]=true;
    }
    for(;vis[f[u]];f[u]++);
    for(int tmp=head[u];tmp;tmp=e[tmp].nxt){
        int v=e[tmp].to;
        if(!mk[v])vis[f[v]]=false;
    }
}

int main(){
	scanf("%d",&n);
	rep (i,1,n) scanf("%d",&fa[i]),adde(fa[i],i);
	int now=1;
	for (;!vis[now];now=fa[now]) vis[now]=1;
	for (;!mk[now];now=fa[now]) mk[now]=1;
	memset(vis,0,sizeof(vis));
	int Mx=0,Mi=1e9;
	rep (i,1,n) if (mk[i]){
		dfs(i);len++;
		Mx=max(Mx,f[i]);
		Mi=min(Mi,f[i]);
	}
	if (Mx==Mi&&(len&1)) puts("IMPOSSIBLE");else puts("POSSIBLE");
	return 0;
}
/*
4
2 3 4 1
*/
### Prompt

Please formulate a CPP solution to 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<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
using namespace std;
#define N 200005
int n,fa[N],cnt,head[N],vis[N],mk[N],f[N],len;
struct edge{int to,nxt;}e[N];
void adde(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
/*void dfs(int u){
	for (int i=head[u];i;i=e[i].nxt) if (!mk[e[i].to]){
		dfs(e[i].to);
		vis[f[e[i].to]]=1;
	}
	int mex=0;while (vis[mex]) mex++;f[u]=mex;
	for (int i=head[u];i;i=e[i].nxt) if (!mk[e[i].to]) vis[f[e[i].to]]=0;
}*/

void dfs(int u){
    for(int tmp=head[u];tmp;tmp=e[tmp].nxt){
        int v=e[tmp].to;
        if(!mk[v])dfs(v);
    }
    for(int tmp=head[u];tmp;tmp=e[tmp].nxt){
        int v=e[tmp].to;
        if(!mk[v])vis[f[v]]=true;
    }
    for(;vis[f[u]];f[u]++);
    for(int tmp=head[u];tmp;tmp=e[tmp].nxt){
        int v=e[tmp].to;
        if(!mk[v])vis[f[v]]=false;
    }
}

int main(){
	scanf("%d",&n);
	rep (i,1,n) scanf("%d",&fa[i]),adde(fa[i],i);
	int now=1;
	for (;!vis[now];now=fa[now]) vis[now]=1;
	for (;!mk[now];now=fa[now]) mk[now]=1;
	memset(vis,0,sizeof(vis));
	int Mx=0,Mi=1e9;
	rep (i,1,n) if (mk[i]){
		dfs(i);len++;
		Mx=max(Mx,f[i]);
		Mi=min(Mi,f[i]);
	}
	if (Mx==Mi&&(len&1)) puts("IMPOSSIBLE");else puts("POSSIBLE");
	return 0;
}
/*
4
2 3 4 1
*/
```