#include<bits/stdc++.h>
#define int long long
using namespace std;
int N;
int p[214514],memo[214514];
vector<int> ve[214514];
int saiki(int u){
	if(memo[u]!=-1)
		return memo[u];
	if(ve[u].empty()){
		memo[u]=0;
		return 0;
	}
	vector<int> gr;
	for(auto x:ve[u])
		gr.push_back(saiki(x));
	sort(begin(gr),end(gr));
	int v=-1;
	for(auto x:gr){
		if(x-v>1)
			break;
		v=x;
	}
	memo[u]=v+1;
	return v+1;
}
signed main(){
	int i,j;
	cin>>N;
	fill(memo,memo+N,-1);
	for(i=0;i<N;i++){
		cin>>p[i];
		p[i]--;
		ve[p[i]].push_back(i);
	}
	int q[214514]={};
	int u=0;
	while(!q[u]){
		q[u]=1;
		u=p[u];
	}
	fill(q,q+N,0);
	while(!q[u]){
		q[u]=1;
		u=p[u];
	}
	for(i=0;i<N;i++)
		if(!q[i])
			saiki(i);
	vector<int> gr;
	int aaa;
	for(auto x:ve[u])
		if(memo[x]!=-1)
			gr.push_back(memo[x]);
		else
			aaa=x;
	sort(begin(gr),end(gr));
	int v=-1;
	for(i=0;i<gr.size();i++){
		if(gr[i]-v>1)
			break;
		v=gr[i];
	}
	v++;
	int w=v;
	for(;i<gr.size();i++){
		if(gr[i]-w>1)
			break;
		w=gr[i];
	}
	w++;
	int hoge[214514];
	copy(memo,memo+N,hoge);
	memo[u]=v;
	if(saiki(aaa)!=v){
		cout<<"POSSIBLE"<<endl;
		return 0;
	}
	copy(hoge,hoge+N,memo);
	memo[u]=w;
	if(saiki(aaa)==v){
		cout<<"POSSIBLE"<<endl;
		return 0;
	}
	cout<<"IMPOSSIBLE"<<endl;
}
### Prompt

Develop a solution in CPP 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<bits/stdc++.h>
#define int long long
using namespace std;
int N;
int p[214514],memo[214514];
vector<int> ve[214514];
int saiki(int u){
	if(memo[u]!=-1)
		return memo[u];
	if(ve[u].empty()){
		memo[u]=0;
		return 0;
	}
	vector<int> gr;
	for(auto x:ve[u])
		gr.push_back(saiki(x));
	sort(begin(gr),end(gr));
	int v=-1;
	for(auto x:gr){
		if(x-v>1)
			break;
		v=x;
	}
	memo[u]=v+1;
	return v+1;
}
signed main(){
	int i,j;
	cin>>N;
	fill(memo,memo+N,-1);
	for(i=0;i<N;i++){
		cin>>p[i];
		p[i]--;
		ve[p[i]].push_back(i);
	}
	int q[214514]={};
	int u=0;
	while(!q[u]){
		q[u]=1;
		u=p[u];
	}
	fill(q,q+N,0);
	while(!q[u]){
		q[u]=1;
		u=p[u];
	}
	for(i=0;i<N;i++)
		if(!q[i])
			saiki(i);
	vector<int> gr;
	int aaa;
	for(auto x:ve[u])
		if(memo[x]!=-1)
			gr.push_back(memo[x]);
		else
			aaa=x;
	sort(begin(gr),end(gr));
	int v=-1;
	for(i=0;i<gr.size();i++){
		if(gr[i]-v>1)
			break;
		v=gr[i];
	}
	v++;
	int w=v;
	for(;i<gr.size();i++){
		if(gr[i]-w>1)
			break;
		w=gr[i];
	}
	w++;
	int hoge[214514];
	copy(memo,memo+N,hoge);
	memo[u]=v;
	if(saiki(aaa)!=v){
		cout<<"POSSIBLE"<<endl;
		return 0;
	}
	copy(hoge,hoge+N,memo);
	memo[u]=w;
	if(saiki(aaa)==v){
		cout<<"POSSIBLE"<<endl;
		return 0;
	}
	cout<<"IMPOSSIBLE"<<endl;
}
```