#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#ifdef _DEBUG_
	#define debug(...) printf(__VA_ARGS__)
#else
	#define debug(...) (void)0
#endif
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;

const int MAXN = 2e5 + 1000;
int p[MAXN];
VI e[MAXN];
int out[MAXN];
int a[MAXN];

int mex(VI &vec) {
	sort(ALL(vec));
	if(SZ(vec) == 0 || vec[0] > 0)
		return 0;
	for(int i = 1; i < SZ(vec); i++)
		if(vec[i - 1] < vec[i] - 1)
			return vec[i - 1] + 1;
	return vec.back() + 1;
}
int v_mex(int v, bool es = false) {
	VI tmp;
	for(int u : e[v]) {
		if(es && out[u] > 0) continue;
		tmp.PB(a[u]);
	}
	return mex(tmp);
}

int main() {
	int N;
	scanf("%d", &N);
	for(int i = 1; i <= N; i++) {
		scanf("%d", &p[i]);
		e[p[i]].PB(i);
		out[p[i]]++;
	}
	VI nxt, tmp;
	for(int i = 1; i <= N; i++)
		if(out[i] == 0)
			nxt.PB(i);
	while(SZ(nxt) > 0) {
		int v = nxt.back(); nxt.pop_back();
		a[v] = v_mex(v);
		out[p[v]]--;
		if(out[p[v]] == 0)
			nxt.PB(p[v]);
	}

	int tar = 0;
	for(int i = 1; i <= N; i++)
		if(out[i] > 0) {
			tar = i;
			break;
		}
	int x;
	x = v_mex(tar, true);

	a[tar] = x;
	int v = p[tar];
	while(v != tar) {
		a[v] = v_mex(v);
		debug("a[%d] = %d\n", v, a[v]);
		v = p[v];
	}
	if(v_mex(tar) == a[tar]) {
		debug("hi 1\n");
		puts("POSSIBLE");
		return 0;
	}

	for(int i = 1; i <= N; i++)
		if(out[i] > 0 && p[i] == tar)
			a[i] = x;
	a[tar] = v_mex(tar);
	v = p[tar];
	while(v != tar) {
		a[v] = v_mex(v);
		v = p[v];
	}
	if(v_mex(tar) == a[tar]) {
		debug("hi 2\n");
		puts("POSSIBLE");
		return 0;
	}
	puts("IMPOSSIBLE");
	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
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#ifdef _DEBUG_
	#define debug(...) printf(__VA_ARGS__)
#else
	#define debug(...) (void)0
#endif
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;

const int MAXN = 2e5 + 1000;
int p[MAXN];
VI e[MAXN];
int out[MAXN];
int a[MAXN];

int mex(VI &vec) {
	sort(ALL(vec));
	if(SZ(vec) == 0 || vec[0] > 0)
		return 0;
	for(int i = 1; i < SZ(vec); i++)
		if(vec[i - 1] < vec[i] - 1)
			return vec[i - 1] + 1;
	return vec.back() + 1;
}
int v_mex(int v, bool es = false) {
	VI tmp;
	for(int u : e[v]) {
		if(es && out[u] > 0) continue;
		tmp.PB(a[u]);
	}
	return mex(tmp);
}

int main() {
	int N;
	scanf("%d", &N);
	for(int i = 1; i <= N; i++) {
		scanf("%d", &p[i]);
		e[p[i]].PB(i);
		out[p[i]]++;
	}
	VI nxt, tmp;
	for(int i = 1; i <= N; i++)
		if(out[i] == 0)
			nxt.PB(i);
	while(SZ(nxt) > 0) {
		int v = nxt.back(); nxt.pop_back();
		a[v] = v_mex(v);
		out[p[v]]--;
		if(out[p[v]] == 0)
			nxt.PB(p[v]);
	}

	int tar = 0;
	for(int i = 1; i <= N; i++)
		if(out[i] > 0) {
			tar = i;
			break;
		}
	int x;
	x = v_mex(tar, true);

	a[tar] = x;
	int v = p[tar];
	while(v != tar) {
		a[v] = v_mex(v);
		debug("a[%d] = %d\n", v, a[v]);
		v = p[v];
	}
	if(v_mex(tar) == a[tar]) {
		debug("hi 1\n");
		puts("POSSIBLE");
		return 0;
	}

	for(int i = 1; i <= N; i++)
		if(out[i] > 0 && p[i] == tar)
			a[i] = x;
	a[tar] = v_mex(tar);
	v = p[tar];
	while(v != tar) {
		a[v] = v_mex(v);
		v = p[v];
	}
	if(v_mex(tar) == a[tar]) {
		debug("hi 2\n");
		puts("POSSIBLE");
		return 0;
	}
	puts("IMPOSSIBLE");
	return 0;
}

```