#include <set>
#include <vector>
#include <iostream>
using namespace std;
int n, x[200009], vis[200009]; bool dp[200009][2]; vector<int> cyc, v, g[200009];
int grundy(int pos) {
	set<int> s;
	for (int i : g[pos]) {
		if(!vis[i]) s.insert(grundy(i));
	}
	int ret = 0;
	while (s.count(ret)) ret++;
	return ret;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> x[i], g[--x[i]].push_back(i);
	int pos = 0;
	while (!vis[pos]) vis[pos] = true, pos = x[pos];
	fill(vis, vis + n, false);
	while (!vis[pos]) vis[pos] = true, cyc.push_back(pos), pos = x[pos];
	for (int i : cyc) v.push_back(grundy(i));
	int c = v.size(); bool flag = false;
	for (int i = 0; i < 2; i++) {
		dp[0][i] = true; dp[0][i ^ 1] = false;
		for (int j = 0; j < c; j++) {
			dp[j + 1][0] = dp[j + 1][1] = false;
			if (dp[j][0]) {
				if (v[(j + 1) % c] != v[j]) dp[j + 1][0] = true;
				if (v[(j + 1) % c] + 1 != v[j]) dp[j + 1][1] = true;
			}
			if(dp[j][1]) {
				if (v[(j + 1) % c] == v[j]) dp[j + 1][0] = true;
				if (v[(j + 1) % c] + 1 == v[j]) dp[j + 1][1] = true;
			}
		}
		if (dp[c][i]) flag = true;
	}
	cout << (flag ? "POSSIBLE" : "IMPOSSIBLE") << endl;
	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 <set>
#include <vector>
#include <iostream>
using namespace std;
int n, x[200009], vis[200009]; bool dp[200009][2]; vector<int> cyc, v, g[200009];
int grundy(int pos) {
	set<int> s;
	for (int i : g[pos]) {
		if(!vis[i]) s.insert(grundy(i));
	}
	int ret = 0;
	while (s.count(ret)) ret++;
	return ret;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> x[i], g[--x[i]].push_back(i);
	int pos = 0;
	while (!vis[pos]) vis[pos] = true, pos = x[pos];
	fill(vis, vis + n, false);
	while (!vis[pos]) vis[pos] = true, cyc.push_back(pos), pos = x[pos];
	for (int i : cyc) v.push_back(grundy(i));
	int c = v.size(); bool flag = false;
	for (int i = 0; i < 2; i++) {
		dp[0][i] = true; dp[0][i ^ 1] = false;
		for (int j = 0; j < c; j++) {
			dp[j + 1][0] = dp[j + 1][1] = false;
			if (dp[j][0]) {
				if (v[(j + 1) % c] != v[j]) dp[j + 1][0] = true;
				if (v[(j + 1) % c] + 1 != v[j]) dp[j + 1][1] = true;
			}
			if(dp[j][1]) {
				if (v[(j + 1) % c] == v[j]) dp[j + 1][0] = true;
				if (v[(j + 1) % c] + 1 == v[j]) dp[j + 1][1] = true;
			}
		}
		if (dp[c][i]) flag = true;
	}
	cout << (flag ? "POSSIBLE" : "IMPOSSIBLE") << endl;
	return 0;
}
```