// 16:32 - 
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define lch (o << 1)
#define rch (o << 1 | 1)

typedef double db;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> pint;

const int N = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;

vector<int> a[N];
bool isCyc[N];
int w[N], from[N];

void FindCycle(int u){
	static int stk[N], vst[N];
	if(vst[u]){
		isCyc[u] = 1;
		while(stk[stk[0]] != u){
			isCyc[stk[stk[0]]] = 1;
			stk[0]--;
		}
		return;
	}
	vst[u] = 1;
	stk[++stk[0]] = u;
	FindCycle(from[u]);
}

void DFS(int u){
	set<int> s;
	for(auto v: a[u]){
		if(w[v] == -1) DFS(v);
		s.insert(w[v]);
	}
	for(int i=0; ; i++)
		if(s.find(i) == s.end()){
			w[u] = i; break;
		}
}

bool Check(int rt, int x){
	int o = from[rt];
	w[rt] = x;
	while(o != rt){
		set<int> s;
		for(auto v: a[o])
			s.insert(w[v]);
		for(int i=0; ; i++)
			if(s.find(i) == s.end()){
				w[o] = i; break;
			}
		o = from[o];
	}
	set<int> s;
	for(auto v: a[rt])
		s.insert(w[v]);
	for(int i=0; ; i++)
		if(s.find(i) == s.end())
			return i == x;
}

int main(){
	ios::sync_with_stdio(0);

	int n; cin >> n;
	for(int i=1; i<=n; i++){
		int u; cin >> u;
		a[u].push_back(i);
		from[i] = u;
	}

	FindCycle(1);

	memset(w, -1, sizeof(w));
	
	int rt = 0;
	for(int i=1; i<=n; i++)
		if(!isCyc[i]) DFS(i);
		else rt = i;
	
	set<int> srt;
	for(auto v: a[rt])
		if(!isCyc[v]) srt.insert(w[v]);
	int v1 = -1, v2 = -1;
	for(int i=0; ; i++){
		if(srt.find(i) != srt.end()) continue;
		if(v1 == -1) v1 = i;
		else{
			v2 = i; break;
		}
	}

	bool f = 1;
	if(!Check(rt, v1) && !Check(rt, v2)) f = 0;
	cout << (f ? "POSSIBLE\n" : "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
// 16:32 - 
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define lch (o << 1)
#define rch (o << 1 | 1)

typedef double db;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> pint;

const int N = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;

vector<int> a[N];
bool isCyc[N];
int w[N], from[N];

void FindCycle(int u){
	static int stk[N], vst[N];
	if(vst[u]){
		isCyc[u] = 1;
		while(stk[stk[0]] != u){
			isCyc[stk[stk[0]]] = 1;
			stk[0]--;
		}
		return;
	}
	vst[u] = 1;
	stk[++stk[0]] = u;
	FindCycle(from[u]);
}

void DFS(int u){
	set<int> s;
	for(auto v: a[u]){
		if(w[v] == -1) DFS(v);
		s.insert(w[v]);
	}
	for(int i=0; ; i++)
		if(s.find(i) == s.end()){
			w[u] = i; break;
		}
}

bool Check(int rt, int x){
	int o = from[rt];
	w[rt] = x;
	while(o != rt){
		set<int> s;
		for(auto v: a[o])
			s.insert(w[v]);
		for(int i=0; ; i++)
			if(s.find(i) == s.end()){
				w[o] = i; break;
			}
		o = from[o];
	}
	set<int> s;
	for(auto v: a[rt])
		s.insert(w[v]);
	for(int i=0; ; i++)
		if(s.find(i) == s.end())
			return i == x;
}

int main(){
	ios::sync_with_stdio(0);

	int n; cin >> n;
	for(int i=1; i<=n; i++){
		int u; cin >> u;
		a[u].push_back(i);
		from[i] = u;
	}

	FindCycle(1);

	memset(w, -1, sizeof(w));
	
	int rt = 0;
	for(int i=1; i<=n; i++)
		if(!isCyc[i]) DFS(i);
		else rt = i;
	
	set<int> srt;
	for(auto v: a[rt])
		if(!isCyc[v]) srt.insert(w[v]);
	int v1 = -1, v2 = -1;
	for(int i=0; ; i++){
		if(srt.find(i) != srt.end()) continue;
		if(v1 == -1) v1 = i;
		else{
			v2 = i; break;
		}
	}

	bool f = 1;
	if(!Check(rt, v1) && !Check(rt, v2)) f = 0;
	cout << (f ? "POSSIBLE\n" : "IMPOSSIBLE\n");

	return 0;
}

```