#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll ;
#define rep(i, a, b) for (int i = a; i <= b; ++ i) 
const int N = 2e5 + 5, M = N << 1 ;
using namespace std ;

bool flg = true ;
int n, e, ter[M], nxt[M], lnk[N], opt[N], mex[N], d[N], pre[N] ;
map <int, bool> h[N] ;

void add(int x, int y) {
	ter[++ e] = y, nxt[e] = lnk[x], lnk[x] = e ;
}

bool cmp(int x, int y) {
	return mex[x] < mex[y] ;
}

void solve(int x) {
	if (d[pre[x]]) {
		if (mex[pre[x]] > mex[x]) ; else solve(pre[x]) ;
	} 
	if (mex[pre[x]] == mex[x]) ++ mex[x] ;
	d[x] = 0 ;
}

int main() {
	scanf("%d", &n) ;
	int x ;
	rep(i, 1, n) scanf("%d", &x), add(x, i), add(i, x), ++ d[x] ;
	int he = 0, ta = 0 ;
	rep(i, 1, n) if (!d[i]) opt[++ ta] = i  ;
	for ( ; he != ta ; ) {
		++ he ;
		int u = opt[he] ;
		for ( ; h[u][mex[u]] ; ++ mex[u]) ;
		for (int i = lnk[u] ; i; i = nxt[i]) if (!(i & 1)) {
			int v = ter[i] ;
			-- d[v] ;
			h[v][mex[u]] = true ;
			if (!d[v]) opt[++ ta] = v ;
		}
	}
	ta = 0 ;
	rep(i, 1, n) if (d[i]) {
		for ( ; h[i][mex[i]] ; ++ mex[i]) ;
		for (int j = lnk[i]; j; j = nxt[j]) if (j & 1) if (d[ter[j]]) pre[i] = ter[j] ;
		opt[++ ta] = i ;
	}
	sort(opt + 1, opt + ta + 1, cmp) ;
	if (mex[opt[1]] == mex[opt[ta]]) {
		if (ta & 1) flg = false ;
	} else {
		rep(i, 1, ta) solve(opt[i]) ;
	}
	if (flg) puts("POSSIBLE") ; else puts("IMPOSSIBLE") ; 
	return 0 ; 
}
### 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 <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll ;
#define rep(i, a, b) for (int i = a; i <= b; ++ i) 
const int N = 2e5 + 5, M = N << 1 ;
using namespace std ;

bool flg = true ;
int n, e, ter[M], nxt[M], lnk[N], opt[N], mex[N], d[N], pre[N] ;
map <int, bool> h[N] ;

void add(int x, int y) {
	ter[++ e] = y, nxt[e] = lnk[x], lnk[x] = e ;
}

bool cmp(int x, int y) {
	return mex[x] < mex[y] ;
}

void solve(int x) {
	if (d[pre[x]]) {
		if (mex[pre[x]] > mex[x]) ; else solve(pre[x]) ;
	} 
	if (mex[pre[x]] == mex[x]) ++ mex[x] ;
	d[x] = 0 ;
}

int main() {
	scanf("%d", &n) ;
	int x ;
	rep(i, 1, n) scanf("%d", &x), add(x, i), add(i, x), ++ d[x] ;
	int he = 0, ta = 0 ;
	rep(i, 1, n) if (!d[i]) opt[++ ta] = i  ;
	for ( ; he != ta ; ) {
		++ he ;
		int u = opt[he] ;
		for ( ; h[u][mex[u]] ; ++ mex[u]) ;
		for (int i = lnk[u] ; i; i = nxt[i]) if (!(i & 1)) {
			int v = ter[i] ;
			-- d[v] ;
			h[v][mex[u]] = true ;
			if (!d[v]) opt[++ ta] = v ;
		}
	}
	ta = 0 ;
	rep(i, 1, n) if (d[i]) {
		for ( ; h[i][mex[i]] ; ++ mex[i]) ;
		for (int j = lnk[i]; j; j = nxt[j]) if (j & 1) if (d[ter[j]]) pre[i] = ter[j] ;
		opt[++ ta] = i ;
	}
	sort(opt + 1, opt + ta + 1, cmp) ;
	if (mex[opt[1]] == mex[opt[ta]]) {
		if (ta & 1) flg = false ;
	} else {
		rep(i, 1, ta) solve(opt[i]) ;
	}
	if (flg) puts("POSSIBLE") ; else puts("IMPOSSIBLE") ; 
	return 0 ; 
}
```