#include<bits/stdc++.h>
using namespace std;
const int N=2050000;
inline int rd(register int x=0,register char ch=getchar(),register int f=0){
	for(;!isdigit(ch);ch=getchar()) f=ch=='-';
	for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+ch-48;
	return f?-x:x;
}
int n,B;
int head[N],to[N<<1],nxt[N<<1],sta[N],vis[N],a[N],al[N];
vector<int> scc;

void lnk(int x,int y){
	to[++B]=y,nxt[B]=head[x],head[x]=B;
}
void dfs(int x,int prt){
	if(vis[x]){
		//printf("-> %d %d %d %d\n",x,prt,vis[x],sta[0]);
		for(int i=vis[x];i<=sta[0];++i) scc.push_back(sta[i]);
		return;
	}
	sta[++sta[0]]=x,vis[x]=sta[0];
	for(int i=head[x];i;i=nxt[i]) if(to[i]!=prt) dfs(to[i],x);
	vis[x]=0;--sta[0];
}
void DFS(int x,int prt){
	for(int i=head[x];i;i=nxt[i]) if(to[i]!=prt&&!vis[to[i]]) DFS(to[i],x);
	for(int i=head[x];i;i=nxt[i]) if(to[i]!=prt&&!vis[to[i]]) al[a[to[i]]]=1;
	while(al[a[x]]) ++a[x];
	for(int i=head[x];i;i=nxt[i]) if(to[i]!=prt&&!vis[to[i]]) al[a[to[i]]]=0;
}
int main(){
	n=rd();
	for(int i=1;i<=n;++i) lnk(rd(),i);
	for(int i=1;i<=n;++i) if(!scc.size()) dfs(i,0);
	for(auto x:scc) vis[x]=1;
	for(auto x:scc) DFS(x,0);
	int mx=-n-100,mn=n+100;
	for(auto x:scc) mx=max(mx,a[x]),mn=min(mn,a[x]);
	puts((mx==mn&&scc.size()%2!=0)?"IMPOSSIBLE":"POSSIBLE");
}
### Prompt

Generate 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>
using namespace std;
const int N=2050000;
inline int rd(register int x=0,register char ch=getchar(),register int f=0){
	for(;!isdigit(ch);ch=getchar()) f=ch=='-';
	for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+ch-48;
	return f?-x:x;
}
int n,B;
int head[N],to[N<<1],nxt[N<<1],sta[N],vis[N],a[N],al[N];
vector<int> scc;

void lnk(int x,int y){
	to[++B]=y,nxt[B]=head[x],head[x]=B;
}
void dfs(int x,int prt){
	if(vis[x]){
		//printf("-> %d %d %d %d\n",x,prt,vis[x],sta[0]);
		for(int i=vis[x];i<=sta[0];++i) scc.push_back(sta[i]);
		return;
	}
	sta[++sta[0]]=x,vis[x]=sta[0];
	for(int i=head[x];i;i=nxt[i]) if(to[i]!=prt) dfs(to[i],x);
	vis[x]=0;--sta[0];
}
void DFS(int x,int prt){
	for(int i=head[x];i;i=nxt[i]) if(to[i]!=prt&&!vis[to[i]]) DFS(to[i],x);
	for(int i=head[x];i;i=nxt[i]) if(to[i]!=prt&&!vis[to[i]]) al[a[to[i]]]=1;
	while(al[a[x]]) ++a[x];
	for(int i=head[x];i;i=nxt[i]) if(to[i]!=prt&&!vis[to[i]]) al[a[to[i]]]=0;
}
int main(){
	n=rd();
	for(int i=1;i<=n;++i) lnk(rd(),i);
	for(int i=1;i<=n;++i) if(!scc.size()) dfs(i,0);
	for(auto x:scc) vis[x]=1;
	for(auto x:scc) DFS(x,0);
	int mx=-n-100,mn=n+100;
	for(auto x:scc) mx=max(mx,a[x]),mn=min(mn,a[x]);
	puts((mx==mn&&scc.size()%2!=0)?"IMPOSSIBLE":"POSSIBLE");
}
```