#include <bits/stdc++.h>
#include <random>
using namespace std;

#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back

typedef long long ll;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef vector<int> vi;

const int MOD = 1e9 + 7;
const int INF = INT_MAX / 2;

bool check(int N, vector<vector<int> > G, vector<int> a) {
	rep(u, N) {
		set<int> st;
		for (int v : G[u]) st.insert(a[v]);
		int x;
		for (x = 0; st.count(x); x++);
		if (x != a[u]) return false;
	}
	return true;
}

int main() {
	int N; cin >> N;
	vector<vector<int> > G(N), _G(N);
	rep(u, N) {
		int v; scanf("%d", &v);
		v--;
		G[v].pb(u);
		_G[u].pb(v);
	}
	rep(z, 2) {
		vector<int> d(N);
		rep(u, N) d[u] = G[u].size();
		vector<int> a(N, -1);
		priority_queue<i_i, vector<i_i>, greater<i_i> > q;
		rep(u, N) q.push(i_i(d[u], u));
		while (q.size()) {
			i_i du = q.top(); q.pop();
			int u = du.second;
			if (du.first > d[u]) continue;
			set<int> st;
			for (int v: G[u]) st.insert(a[v]);
			int x;
			bool hoge = true;
			for (x = 0; ; x++) {
				if (st.count(x)) continue;
				if (d[u] && z && hoge) {
					hoge = false;
					continue;
				}
				break;
			}
			a[u] = x;
			for (int v: _G[u]) {
				d[v]--;
				if (a[v] == -1) q.push(i_i(d[v], v));
			}
		}
		if (check(N, G, a)) {
			cout << "POSSIBLE" << endl;
			return 0;
		}
	}
	cout << "IMPOSSIBLE" << endl;
}

### Prompt

Please formulate 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>
#include <random>
using namespace std;

#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back

typedef long long ll;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef vector<int> vi;

const int MOD = 1e9 + 7;
const int INF = INT_MAX / 2;

bool check(int N, vector<vector<int> > G, vector<int> a) {
	rep(u, N) {
		set<int> st;
		for (int v : G[u]) st.insert(a[v]);
		int x;
		for (x = 0; st.count(x); x++);
		if (x != a[u]) return false;
	}
	return true;
}

int main() {
	int N; cin >> N;
	vector<vector<int> > G(N), _G(N);
	rep(u, N) {
		int v; scanf("%d", &v);
		v--;
		G[v].pb(u);
		_G[u].pb(v);
	}
	rep(z, 2) {
		vector<int> d(N);
		rep(u, N) d[u] = G[u].size();
		vector<int> a(N, -1);
		priority_queue<i_i, vector<i_i>, greater<i_i> > q;
		rep(u, N) q.push(i_i(d[u], u));
		while (q.size()) {
			i_i du = q.top(); q.pop();
			int u = du.second;
			if (du.first > d[u]) continue;
			set<int> st;
			for (int v: G[u]) st.insert(a[v]);
			int x;
			bool hoge = true;
			for (x = 0; ; x++) {
				if (st.count(x)) continue;
				if (d[u] && z && hoge) {
					hoge = false;
					continue;
				}
				break;
			}
			a[u] = x;
			for (int v: _G[u]) {
				d[v]--;
				if (a[v] == -1) q.push(i_i(d[v], v));
			}
		}
		if (check(N, G, a)) {
			cout << "POSSIBLE" << endl;
			return 0;
		}
	}
	cout << "IMPOSSIBLE" << endl;
}

```