#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
int p[200100];
bool use[200100],u2[200100];
vector<int> gr[200100];
vector<int> ch[200100];
int m;
int cal(vector<int> x){
	x.pb(-1);x.pb(200100);
	sort(All(x));
	rep(i,x.size()-1){
		if(x[i]<x[i+1]-1) return x[i]+1;
	}
}
int dfs(int v){
	vector<int> x;
	rep(i,gr[v].size()) x.pb(dfs(gr[v][i]));
	return cal(x);
}
bool che(int a){
	int now=a;
	rep(i,m){
		vector<int> v=ch[i];
		v.pb(now);
		now=cal(v);
	}
	return (now==a);
}
int main()
{
	int n,c;
	vector<int> fl;
	cin>>n;
	rep(i,n){
		cin>>p[i];p[i]--;
		gr[p[i]].pb(i);
	}
	memset(use,false,sizeof(use));
	int now=0;
	while(!use[now]){
		use[now]=true;now=p[now];
	}
	memset(use,false,sizeof(use));
	while(!use[now]){
		fl.pb(now);use[now]=true;now=p[now];
	}
	m=fl.size();
	rep(i,m){
		rep(j,gr[fl[i]].size()){
			int v=gr[fl[i]][j];
			if(!use[v]) ch[i].pb(dfs(v));
		}
	}
	memset(u2,false,sizeof(u2));
	rep(i,ch[m-1].size()) u2[ch[m-1][i]]=true;
	vector<int> ca;
	rep(i,200100){
		if(!u2[i]) ca.pb(i);
	}
	if(che(ca[0])) cout<<"POSSIBLE"<<endl;
	else if(che(ca[1])) cout<<"POSSIBLE"<<endl;
	else cout<<"IMPOSSIBLE"<<endl;
}

### 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<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
int p[200100];
bool use[200100],u2[200100];
vector<int> gr[200100];
vector<int> ch[200100];
int m;
int cal(vector<int> x){
	x.pb(-1);x.pb(200100);
	sort(All(x));
	rep(i,x.size()-1){
		if(x[i]<x[i+1]-1) return x[i]+1;
	}
}
int dfs(int v){
	vector<int> x;
	rep(i,gr[v].size()) x.pb(dfs(gr[v][i]));
	return cal(x);
}
bool che(int a){
	int now=a;
	rep(i,m){
		vector<int> v=ch[i];
		v.pb(now);
		now=cal(v);
	}
	return (now==a);
}
int main()
{
	int n,c;
	vector<int> fl;
	cin>>n;
	rep(i,n){
		cin>>p[i];p[i]--;
		gr[p[i]].pb(i);
	}
	memset(use,false,sizeof(use));
	int now=0;
	while(!use[now]){
		use[now]=true;now=p[now];
	}
	memset(use,false,sizeof(use));
	while(!use[now]){
		fl.pb(now);use[now]=true;now=p[now];
	}
	m=fl.size();
	rep(i,m){
		rep(j,gr[fl[i]].size()){
			int v=gr[fl[i]][j];
			if(!use[v]) ch[i].pb(dfs(v));
		}
	}
	memset(u2,false,sizeof(u2));
	rep(i,ch[m-1].size()) u2[ch[m-1][i]]=true;
	vector<int> ca;
	rep(i,200100){
		if(!u2[i]) ca.pb(i);
	}
	if(che(ca[0])) cout<<"POSSIBLE"<<endl;
	else if(che(ca[1])) cout<<"POSSIBLE"<<endl;
	else cout<<"IMPOSSIBLE"<<endl;
}

```