#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int Q=230123;
int las[Q],e[Q<<1],nn[Q<<1];
int inc=0;
void ins(int x,int y)
{
	e[++inc]=y;
	nn[inc]=las[x];
	las[x]=inc;
}
int Time=0;
int vis[Q];
int flag;
int fa[Q];
int cir[Q]={0},tot=0;
int isrt[Q];
void ddd(int x)
{
	if(flag)return;
	vis[x]=Time;
	if(vis[fa[x]]){
		if(vis[fa[x]]==vis[x]){
			int t=x;
			do{
				cir[++tot]=t;
				isrt[t]=1;
				t=fa[t];
			}while(t!=x);
		}
		return;
	}
	ddd(fa[x]);
}
int mx[Q];
int cnt[Q];
void dfs(int x)
{
	for(int t=las[x];t;t=nn[t]){
		int y=e[t];
		if(isrt[y])continue;
		dfs(y);
	}
	++Time;
	for(int t=las[x];t;t=nn[t]){
		int y=e[t];
		if(isrt[y])continue;
		cnt[mx[y]]=Time;
	}
	for(mx[x]=0;cnt[mx[x]]==Time;++mx[x]);
}
int main()
{
	int n;
	int x;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&x),ins(x,i),fa[i]=x;
	for(int i=1;i<=n;i++)
		if(!vis[i])++Time,ddd(i);
	Time=0;
	if(tot%2==0)return puts("POSSIBLE")&0;
	for(int i=1;i<=tot;i++)
		dfs(cir[i]);
	for(int i=2;i<=tot;i++)
		if(mx[cir[i]]!=mx[cir[i-1]])
		return puts("POSSIBLE")&0;
	puts("IMPOSSIBLE");
	return 0;
}
### Prompt

Your task is to create 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 <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int Q=230123;
int las[Q],e[Q<<1],nn[Q<<1];
int inc=0;
void ins(int x,int y)
{
	e[++inc]=y;
	nn[inc]=las[x];
	las[x]=inc;
}
int Time=0;
int vis[Q];
int flag;
int fa[Q];
int cir[Q]={0},tot=0;
int isrt[Q];
void ddd(int x)
{
	if(flag)return;
	vis[x]=Time;
	if(vis[fa[x]]){
		if(vis[fa[x]]==vis[x]){
			int t=x;
			do{
				cir[++tot]=t;
				isrt[t]=1;
				t=fa[t];
			}while(t!=x);
		}
		return;
	}
	ddd(fa[x]);
}
int mx[Q];
int cnt[Q];
void dfs(int x)
{
	for(int t=las[x];t;t=nn[t]){
		int y=e[t];
		if(isrt[y])continue;
		dfs(y);
	}
	++Time;
	for(int t=las[x];t;t=nn[t]){
		int y=e[t];
		if(isrt[y])continue;
		cnt[mx[y]]=Time;
	}
	for(mx[x]=0;cnt[mx[x]]==Time;++mx[x]);
}
int main()
{
	int n;
	int x;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&x),ins(x,i),fa[i]=x;
	for(int i=1;i<=n;i++)
		if(!vis[i])++Time,ddd(i);
	Time=0;
	if(tot%2==0)return puts("POSSIBLE")&0;
	for(int i=1;i<=tot;i++)
		dfs(cir[i]);
	for(int i=2;i<=tot;i++)
		if(mx[cir[i]]!=mx[cir[i-1]])
		return puts("POSSIBLE")&0;
	puts("IMPOSSIBLE");
	return 0;
}
```