#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <stack>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)

const int N=200005;

std:: stack <int> stack;
std:: vector <int> vec;

struct edge {int x,y,next;} e[N*2];

int used[N],dep[N],ls[N],p[N],f[N],d,wjp,edCnt=1;

bool vis[N],in[N];

int read() {
	int x=0,v=1; char ch=getchar();
	for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):v,ch=getchar());
	for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
	return x*v;
}

void add_edge(int x,int y) {
	e[++edCnt]=(edge) {x,y,ls[x]}; ls[x]=edCnt;
}

void dfs1(int x) {
	stack.push(x);
	for (int i=ls[x];i;i=e[i].next) {
		if (!vis[e[i].y]) {
			vis[e[i].y]=1;
			dep[e[i].y]=dep[x]+1;
			dfs1(e[i].y);
		} else {
			int y=0;
			while (y!=e[i].y) {
				y=stack.top(),stack.pop();
				vec.push_back(y);
				in[y]=1;
			}
		}
	}
}

void dfs2(int x,int from) {
	for (int i=ls[x];i;i=e[i].next) {
		if (!in[e[i].y]&&e[i].y!=from) dfs2(e[i].y,x);
	}
	++wjp;
	for (int i=ls[x];i;i=e[i].next) {
		if (!in[e[i].y]&&e[i].y!=from) {
			used[f[e[i].y]]=wjp;
		}
	}
	for (f[x]=0;used[f[x]]==wjp;) f[x]++;
}

int main(void) {
	int n=read(),rec=-1;
	rep(i,1,n) p[i]=read();
	rep(i,1,n) add_edge(i,p[i]);
	dep[1]=vis[1]=1;
	dfs1(1);
	rep(i,1,n) add_edge(p[i],i);
	bool flag=false;
	for (int x:vec) {
		dfs2(x,0);
		if (rec==-1) rec=f[x];
		else if (rec!=f[x]) flag=true;
	}
	if ((vec.size()&1)&&(!flag)) puts("IMPOSSIBLE");
	else puts("POSSIBLE");
	return 0;
}
### Prompt

Please create a solution in CPP 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 <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <stack>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)

const int N=200005;

std:: stack <int> stack;
std:: vector <int> vec;

struct edge {int x,y,next;} e[N*2];

int used[N],dep[N],ls[N],p[N],f[N],d,wjp,edCnt=1;

bool vis[N],in[N];

int read() {
	int x=0,v=1; char ch=getchar();
	for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):v,ch=getchar());
	for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
	return x*v;
}

void add_edge(int x,int y) {
	e[++edCnt]=(edge) {x,y,ls[x]}; ls[x]=edCnt;
}

void dfs1(int x) {
	stack.push(x);
	for (int i=ls[x];i;i=e[i].next) {
		if (!vis[e[i].y]) {
			vis[e[i].y]=1;
			dep[e[i].y]=dep[x]+1;
			dfs1(e[i].y);
		} else {
			int y=0;
			while (y!=e[i].y) {
				y=stack.top(),stack.pop();
				vec.push_back(y);
				in[y]=1;
			}
		}
	}
}

void dfs2(int x,int from) {
	for (int i=ls[x];i;i=e[i].next) {
		if (!in[e[i].y]&&e[i].y!=from) dfs2(e[i].y,x);
	}
	++wjp;
	for (int i=ls[x];i;i=e[i].next) {
		if (!in[e[i].y]&&e[i].y!=from) {
			used[f[e[i].y]]=wjp;
		}
	}
	for (f[x]=0;used[f[x]]==wjp;) f[x]++;
}

int main(void) {
	int n=read(),rec=-1;
	rep(i,1,n) p[i]=read();
	rep(i,1,n) add_edge(i,p[i]);
	dep[1]=vis[1]=1;
	dfs1(1);
	rep(i,1,n) add_edge(p[i],i);
	bool flag=false;
	for (int x:vec) {
		dfs2(x,0);
		if (rec==-1) rec=f[x];
		else if (rec!=f[x]) flag=true;
	}
	if ((vec.size()&1)&&(!flag)) puts("IMPOSSIBLE");
	else puts("POSSIBLE");
	return 0;
}
```