#include <bits/stdc++.h>
#define pb push_back
#define LL long long
using namespace std;
const int MAXN = 200005;
vector< int >e[MAXN];
int n, c[MAXN], m, dep[MAXN], fa[MAXN];
bool flg[MAXN];
void ser(int u, int ff) {
	dep[u] = dep[fa[u]=ff] + 1;
	for(auto v : e[u]) if(v != ff) {
		if(!dep[v]) ser(v, u);
		else if(dep[v] < dep[u])
			for(int j = u; ; j = fa[j]) { flg[c[++m] = j] = 1; if(j == v) break; }
	}
}
int a[MAXN], tim, vis[MAXN];
void dfs(int u, int ff) {
	for(auto v : e[u]) if(v != ff && !flg[v]) dfs(v, u);
	++tim;
	for(auto v : e[u]) if(v != ff && !flg[v]) vis[a[v]] = tim;
	for(a[u] = 0; vis[a[u]] == tim; ++a[u]);
}
int main () {
	scanf("%d", &n);
	for(int i = 1, x; i <= n; ++i)
		scanf("%d", &x), e[x].pb(i), e[i].pb(x);
	ser(1, 0);
	bool flg = 1;
	for(int i = 1; i <= m; ++i) {
		dfs(c[i], 0);
		if(a[c[i]] != a[c[1]]) flg = 0;
	}
	if(!flg || !(m&1)) puts("POSSIBLE");
	else puts("IMPOSSIBLE");
}
### 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 pb push_back
#define LL long long
using namespace std;
const int MAXN = 200005;
vector< int >e[MAXN];
int n, c[MAXN], m, dep[MAXN], fa[MAXN];
bool flg[MAXN];
void ser(int u, int ff) {
	dep[u] = dep[fa[u]=ff] + 1;
	for(auto v : e[u]) if(v != ff) {
		if(!dep[v]) ser(v, u);
		else if(dep[v] < dep[u])
			for(int j = u; ; j = fa[j]) { flg[c[++m] = j] = 1; if(j == v) break; }
	}
}
int a[MAXN], tim, vis[MAXN];
void dfs(int u, int ff) {
	for(auto v : e[u]) if(v != ff && !flg[v]) dfs(v, u);
	++tim;
	for(auto v : e[u]) if(v != ff && !flg[v]) vis[a[v]] = tim;
	for(a[u] = 0; vis[a[u]] == tim; ++a[u]);
}
int main () {
	scanf("%d", &n);
	for(int i = 1, x; i <= n; ++i)
		scanf("%d", &x), e[x].pb(i), e[i].pb(x);
	ser(1, 0);
	bool flg = 1;
	for(int i = 1; i <= m; ++i) {
		dfs(c[i], 0);
		if(a[c[i]] != a[c[1]]) flg = 0;
	}
	if(!flg || !(m&1)) puts("POSSIBLE");
	else puts("IMPOSSIBLE");
}
```