#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int N = 2e+5+5;

int n;
int p[N];
bool vis[N];
int a[N],k;
int lef[N],rig[N],val[N];
bool bz[N];
bool ext[N];
int m,b[N];

int solveb(){
	if (!m)return 0;
	sort(b+1,b+1+m);
	int m_=1;
	fo(i,2,m)if (b[i]>b[i-1])b[++m_]=b[i];
	m=m_;
	int ans=m;
	fo(i,1,m)
	if (b[i]!=i-1){ans=i-1;break;}
	return ans;
}

void dfs(int x){
	for(int y=lef[x];y;y=rig[y])dfs(y);
	m=0;
	for(int y=lef[x];y;y=rig[y])b[++m]=val[y];
	val[x]=solveb();
}

bool check(int v){
	val[a[1]]=v;
	fo(i,2,k){
		b[m=1]=val[a[i-1]];
		for(int y=lef[a[i]];y;y=rig[y])b[++m]=val[y];
		val[a[i]]=solveb();
	}
	b[m=1]=val[a[k]];
	for(int y=lef[a[1]];y;y=rig[y])b[++m]=val[y];
	int tmp=solveb();
	return tmp==val[a[1]];
}

int main(){
	n=get();
	fo(i,1,n)p[i]=get();
	int x=1;
	for(;!vis[x];x=p[x])vis[x]=1;
	for(;!k||x!=a[1];x=p[x])a[++k]=x;
	fo(i,1,k)bz[a[i]]=1;
	fo(i,1,n)
	if (!bz[i]){
		rig[i]=lef[p[i]];
		lef[p[i]]=i;
	}
	fo(i,1,k)dfs(a[i]);
	if (check(val[a[1]]))return printf("POSSIBLE\n"),0;
	fo(i,0,n)ext[i]=0;
	for(int y=lef[a[1]];y;y=rig[y])ext[val[y]]=1;
	ext[val[a[1]]]=1;
	int key;
	fo(i,0,n)
	if (!ext[i]){key=i;break;}
	if (check(key))return printf("POSSIBLE\n"),0;
	printf("IMPOSSIBLE\n");
	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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int N = 2e+5+5;

int n;
int p[N];
bool vis[N];
int a[N],k;
int lef[N],rig[N],val[N];
bool bz[N];
bool ext[N];
int m,b[N];

int solveb(){
	if (!m)return 0;
	sort(b+1,b+1+m);
	int m_=1;
	fo(i,2,m)if (b[i]>b[i-1])b[++m_]=b[i];
	m=m_;
	int ans=m;
	fo(i,1,m)
	if (b[i]!=i-1){ans=i-1;break;}
	return ans;
}

void dfs(int x){
	for(int y=lef[x];y;y=rig[y])dfs(y);
	m=0;
	for(int y=lef[x];y;y=rig[y])b[++m]=val[y];
	val[x]=solveb();
}

bool check(int v){
	val[a[1]]=v;
	fo(i,2,k){
		b[m=1]=val[a[i-1]];
		for(int y=lef[a[i]];y;y=rig[y])b[++m]=val[y];
		val[a[i]]=solveb();
	}
	b[m=1]=val[a[k]];
	for(int y=lef[a[1]];y;y=rig[y])b[++m]=val[y];
	int tmp=solveb();
	return tmp==val[a[1]];
}

int main(){
	n=get();
	fo(i,1,n)p[i]=get();
	int x=1;
	for(;!vis[x];x=p[x])vis[x]=1;
	for(;!k||x!=a[1];x=p[x])a[++k]=x;
	fo(i,1,k)bz[a[i]]=1;
	fo(i,1,n)
	if (!bz[i]){
		rig[i]=lef[p[i]];
		lef[p[i]]=i;
	}
	fo(i,1,k)dfs(a[i]);
	if (check(val[a[1]]))return printf("POSSIBLE\n"),0;
	fo(i,0,n)ext[i]=0;
	for(int y=lef[a[1]];y;y=rig[y])ext[val[y]]=1;
	ext[val[a[1]]]=1;
	int key;
	fo(i,0,n)
	if (!ext[i]){key=i;break;}
	if (check(key))return printf("POSSIBLE\n"),0;
	printf("IMPOSSIBLE\n");
	return 0;
}
```