//#pragma GCC optimize(3)
#include<iostream>
#include<iomanip>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#define ll long long
#define db double
#define inf 200009
#define INF (ll)1e15
#define mod ((ll)1e9+7)
#define pi acos(-1)
#define rd(n) {n=0;char ch;int f=0;do{ch=getchar();if(ch=='-'){f=1;}}while(ch<'0'||ch>'9');while('0'<=ch&&ch<='9'){n=(n<<1)+(n<<3)+ch-48;ch=getchar();}if(f)n=-n;}
using namespace std;
int n,m;

struct edge{
	int y,nxt;
	edge(){}
	edge(int yy,int nn){
		y=yy,nxt=nn;
	}
}e[inf*2];
int head[inf],ecnt;

void addedge(int x,int y){
	ecnt++;
	e[ecnt]=edge(y,head[x]);
	head[x]=ecnt;
	return;
}

int fa[inf],val[inf],p[inf],vis[inf],num;

bool dfs(int u){
	for (int i=head[u];i;i=e[i].nxt){
		int v=e[i].y;
		if (!p[v]){
			dfs(v);
		}
	}
	num++;
	for (int i=head[u];i;i=e[i].nxt){
		int v=e[i].y;
		if (!p[v]){
			vis[val[v]]=num;
		}
	}
	val[u]=0;
	while (vis[val[u]]==num){
		val[u]++;
	}
	return p;
}

int main(){
	rd(n)
	int x,y;
	for (int i=1;i<=n;i++){
		rd(fa[i])
		addedge(fa[i],i);
	}
	int now=1,cnt=0;
	while (!p[now]){
		p[now]=1;
		now=fa[now];
	}
	memset(p,0,sizeof(p));
	while (!p[now]){
		p[now]=1;
		cnt++;
		now=fa[now];
	}
	int minv=n+1,maxv=0;
	for (int i=1;i<=n;i++){
		if (p[i]){
			dfs(i);
			maxv=max(maxv,val[i]);
			minv=min(minv,val[i]);
		}
	}
	if (maxv!=minv || !(cnt&1)){
		puts("POSSIBLE");
	}
	else{
		puts("IMPOSSIBLE");
	}
	return 0;
}
### Prompt

In cpp, your task is to solve 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
//#pragma GCC optimize(3)
#include<iostream>
#include<iomanip>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#define ll long long
#define db double
#define inf 200009
#define INF (ll)1e15
#define mod ((ll)1e9+7)
#define pi acos(-1)
#define rd(n) {n=0;char ch;int f=0;do{ch=getchar();if(ch=='-'){f=1;}}while(ch<'0'||ch>'9');while('0'<=ch&&ch<='9'){n=(n<<1)+(n<<3)+ch-48;ch=getchar();}if(f)n=-n;}
using namespace std;
int n,m;

struct edge{
	int y,nxt;
	edge(){}
	edge(int yy,int nn){
		y=yy,nxt=nn;
	}
}e[inf*2];
int head[inf],ecnt;

void addedge(int x,int y){
	ecnt++;
	e[ecnt]=edge(y,head[x]);
	head[x]=ecnt;
	return;
}

int fa[inf],val[inf],p[inf],vis[inf],num;

bool dfs(int u){
	for (int i=head[u];i;i=e[i].nxt){
		int v=e[i].y;
		if (!p[v]){
			dfs(v);
		}
	}
	num++;
	for (int i=head[u];i;i=e[i].nxt){
		int v=e[i].y;
		if (!p[v]){
			vis[val[v]]=num;
		}
	}
	val[u]=0;
	while (vis[val[u]]==num){
		val[u]++;
	}
	return p;
}

int main(){
	rd(n)
	int x,y;
	for (int i=1;i<=n;i++){
		rd(fa[i])
		addedge(fa[i],i);
	}
	int now=1,cnt=0;
	while (!p[now]){
		p[now]=1;
		now=fa[now];
	}
	memset(p,0,sizeof(p));
	while (!p[now]){
		p[now]=1;
		cnt++;
		now=fa[now];
	}
	int minv=n+1,maxv=0;
	for (int i=1;i<=n;i++){
		if (p[i]){
			dfs(i);
			maxv=max(maxv,val[i]);
			minv=min(minv,val[i]);
		}
	}
	if (maxv!=minv || !(cnt&1)){
		puts("POSSIBLE");
	}
	else{
		puts("IMPOSSIBLE");
	}
	return 0;
}
```