#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}

int N;
vector<int> p;
vector<vector<int>> G;

vector<int> getcycle(){
	int v = 0;
	rep(i,N) v = p[v];
	vector<int> ret;
	int o = v;
	do{
		ret.pb(v);
		v = p[v];
	}while(v!=o);
	reverse(all(ret));
	return ret;
}

int getval(int v,int p=-1){
	set<int> st;
	for(int u:G[v]) if(u!=p){
		st.insert(getval(u));
	}
	rep(i,N+10){
		if(!st.count(i)) return i;
	}
}

int main(){
	cin>>N;
	p.resize(N);
	G.resize(N);
	rep(i,N){
		cin>>p[i];p[i]--;
		G[p[i]].pb(i);
	}
	vector<int> cycle = getcycle();

	vector<int> vals;
	int K = cycle.size();
	rep(i,K){
		int v = cycle[i];
		int u = cycle[(i+1)%K];
		vals.pb(getval(v,u));
	}
	reverse(all(vals));
	rep(t,2){
		vector<int> x = vals;
		x[0] += t;
		x.pb(x[0]);
		rep1(i,K){
			if(x[i]==x[i-1]) x[i]++;
		}
		if(x[0]==x[K]){
			puts("POSSIBLE");
			return 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 <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}

int N;
vector<int> p;
vector<vector<int>> G;

vector<int> getcycle(){
	int v = 0;
	rep(i,N) v = p[v];
	vector<int> ret;
	int o = v;
	do{
		ret.pb(v);
		v = p[v];
	}while(v!=o);
	reverse(all(ret));
	return ret;
}

int getval(int v,int p=-1){
	set<int> st;
	for(int u:G[v]) if(u!=p){
		st.insert(getval(u));
	}
	rep(i,N+10){
		if(!st.count(i)) return i;
	}
}

int main(){
	cin>>N;
	p.resize(N);
	G.resize(N);
	rep(i,N){
		cin>>p[i];p[i]--;
		G[p[i]].pb(i);
	}
	vector<int> cycle = getcycle();

	vector<int> vals;
	int K = cycle.size();
	rep(i,K){
		int v = cycle[i];
		int u = cycle[(i+1)%K];
		vals.pb(getval(v,u));
	}
	reverse(all(vals));
	rep(t,2){
		vector<int> x = vals;
		x[0] += t;
		x.pb(x[0]);
		rep1(i,K){
			if(x[i]==x[i-1]) x[i]++;
		}
		if(x[0]==x[K]){
			puts("POSSIBLE");
			return 0;
		}
	}
	puts("IMPOSSIBLE");
	return 0;
}

```