#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define MX 400005

using namespace std;

int v[MX],rud[MX];
int num[MX];
vector<int>son[MX];
int may[MX][2];
int n;

void input()
{
	int f;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&f);
		v[i]=f;
		rud[f]++;
	}
}

int mex(int y)
{
	sort(son[y].begin(),son[y].end());
	if(!son[y].size())return 0;
	else if(son[y][0]!=0)return 0;
	else
	{
		int p=1;
		while(p<son[y].size()&&son[y][p]-son[y][p-1]<=1)p++;
		return son[y][p-1]+1;
	}
}

int stk[MX],top;
void topo()
{
	int x,y;
	for(int i=1;i<=n;i++)if(!rud[i])stk[++top]=i;
	while(top)
	{
		x=stk[top--];
		y=v[x];
		rud[y]--;
		son[y].push_back(num[x]);
		if(!rud[y])
		{
			num[y]=mex(y);
			stk[++top]=y;
		}
	}
}

int work()
{
	int x=0,siz=0,num;
	for(int i=1;i<=n;i++)
	{
		if(rud[i])
		{
			x=i,siz++;
			//for(int j=0;j<son[i].size();j++)cout<<son[i][j]<<" ";cout<<endl;
			//cout<<"fuck:";
			may[i][0]=mex(i);//cout<<endl;
			son[i].push_back(may[i][0]);
			//for(int j=0;j<son[i].size();j++)cout<<son[i][j]<<" ";cout<<endl;
			may[i][1]=mex(i);
			//cout<<i<<" : "<<may[i][0]<<" "<<may[i][1]<<endl;
		}
	}
	num=may[x][0];
	for(int i=1;i<=siz;i++)
	{
		x=v[x];
		if(num==may[x][0])num=may[x][1];
		else num=may[x][0];
	}
	if(num==may[x][0])return 1;
	num=may[x][1];
	for(int i=1;i<=siz;i++)
	{
		x=v[x];
		if(num==may[x][0])num=may[x][1];
		else num=may[x][0];
	}
	if(num==may[x][1])return 1;
	return 0;
}

int main()
{
	input();
	topo();
	if(work())printf("POSSIBLE\n");
	else printf("IMPOSSIBLE\n");
	return 0;
}
### Prompt

Please provide a CPP coded solution to the problem described below:

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 <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define MX 400005

using namespace std;

int v[MX],rud[MX];
int num[MX];
vector<int>son[MX];
int may[MX][2];
int n;

void input()
{
	int f;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&f);
		v[i]=f;
		rud[f]++;
	}
}

int mex(int y)
{
	sort(son[y].begin(),son[y].end());
	if(!son[y].size())return 0;
	else if(son[y][0]!=0)return 0;
	else
	{
		int p=1;
		while(p<son[y].size()&&son[y][p]-son[y][p-1]<=1)p++;
		return son[y][p-1]+1;
	}
}

int stk[MX],top;
void topo()
{
	int x,y;
	for(int i=1;i<=n;i++)if(!rud[i])stk[++top]=i;
	while(top)
	{
		x=stk[top--];
		y=v[x];
		rud[y]--;
		son[y].push_back(num[x]);
		if(!rud[y])
		{
			num[y]=mex(y);
			stk[++top]=y;
		}
	}
}

int work()
{
	int x=0,siz=0,num;
	for(int i=1;i<=n;i++)
	{
		if(rud[i])
		{
			x=i,siz++;
			//for(int j=0;j<son[i].size();j++)cout<<son[i][j]<<" ";cout<<endl;
			//cout<<"fuck:";
			may[i][0]=mex(i);//cout<<endl;
			son[i].push_back(may[i][0]);
			//for(int j=0;j<son[i].size();j++)cout<<son[i][j]<<" ";cout<<endl;
			may[i][1]=mex(i);
			//cout<<i<<" : "<<may[i][0]<<" "<<may[i][1]<<endl;
		}
	}
	num=may[x][0];
	for(int i=1;i<=siz;i++)
	{
		x=v[x];
		if(num==may[x][0])num=may[x][1];
		else num=may[x][0];
	}
	if(num==may[x][0])return 1;
	num=may[x][1];
	for(int i=1;i<=siz;i++)
	{
		x=v[x];
		if(num==may[x][0])num=may[x][1];
		else num=may[x][0];
	}
	if(num==may[x][1])return 1;
	return 0;
}

int main()
{
	input();
	topo();
	if(work())printf("POSSIBLE\n");
	else printf("IMPOSSIBLE\n");
	return 0;
}
```