#include <bits/stdc++.h>

#define For(i, l, r) for (register int i = (l), i##end = int(r); i <= i##end; ++i)
#define Fordown(i, r, l) for (register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Rep(i, r) for (register int i = (0), i##end = int(r); i < i##end; ++i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl

using namespace std;

template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }

inline int read() {
	int x(0), sgn(1); char ch(getchar());
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
	for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
	return x * sgn;
}

void File() {
#ifdef zjp_shadow
	freopen ("F.in", "r", stdin);
	freopen ("F.out", "w", stdout);
#endif
}

const int N = 2e5 + 1e3;

vector<int> G[N]; int mex[N], n, p[N];

bool vis[N], cir[N], app[N];

void Dfs(int u) {
	for (int v : G[u]) if (!cir[v]) Dfs(v);
	for (int v : G[u]) if (!cir[v]) app[mex[v]] = true;
	while (app[mex[u]]) ++ mex[u];
	for (int v : G[u]) app[mex[v]] = false;
}

int main () {

	File();

	n = read();
	For (i, 1, n)
		G[p[i] = read()].push_back(i);

	int x = 1;
	for (; !vis[x]; x = p[x]) vis[x] = true;
	for (; !cir[x]; x = p[x]) cir[x] = true;

	int minv = n + 1, maxv = 0, cnt = 0;

	For (i, 1, n) if (cir[i])
		Dfs(i), ++ cnt, chkmax(maxv, mex[i]), chkmin(minv, mex[i]);

	puts(maxv == minv && (cnt & 1) ? "IMPOSSIBLE" : "POSSIBLE");

	return 0;

}
### Prompt

Develop a solution in cpp to the problem described below:

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 For(i, l, r) for (register int i = (l), i##end = int(r); i <= i##end; ++i)
#define Fordown(i, r, l) for (register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Rep(i, r) for (register int i = (0), i##end = int(r); i < i##end; ++i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl

using namespace std;

template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }

inline int read() {
	int x(0), sgn(1); char ch(getchar());
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
	for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
	return x * sgn;
}

void File() {
#ifdef zjp_shadow
	freopen ("F.in", "r", stdin);
	freopen ("F.out", "w", stdout);
#endif
}

const int N = 2e5 + 1e3;

vector<int> G[N]; int mex[N], n, p[N];

bool vis[N], cir[N], app[N];

void Dfs(int u) {
	for (int v : G[u]) if (!cir[v]) Dfs(v);
	for (int v : G[u]) if (!cir[v]) app[mex[v]] = true;
	while (app[mex[u]]) ++ mex[u];
	for (int v : G[u]) app[mex[v]] = false;
}

int main () {

	File();

	n = read();
	For (i, 1, n)
		G[p[i] = read()].push_back(i);

	int x = 1;
	for (; !vis[x]; x = p[x]) vis[x] = true;
	for (; !cir[x]; x = p[x]) cir[x] = true;

	int minv = n + 1, maxv = 0, cnt = 0;

	For (i, 1, n) if (cir[i])
		Dfs(i), ++ cnt, chkmax(maxv, mex[i]), chkmin(minv, mex[i]);

	puts(maxv == minv && (cnt & 1) ? "IMPOSSIBLE" : "POSSIBLE");

	return 0;

}
```