#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <ctime>

#define Rep(i, n) for (int i = 1; i <= n; i ++)
#define Rep0(i, n) for (int i = 0; i <= n; i ++)
#define RepG(i, x) for (int i = head[x]; i; i = edge[i].next)
#define v edge[i].to
#define mp(a, b) make_pair(a, b)

using namespace std;

const int N = 200010;

struct Edge{ int to, next;} edge[N];
int head[N], num, p[N];
void add_edge(int a, int b) { edge[++ num] = (Edge){b, head[a]}, head[a] = num;}
int sg[N];
vector<int> h;
void dfs(int x)
{
	//printf("%d\n", x);
	RepG(i, x) dfs(v);
	RepG(i, x) h.push_back(sg[v]);
	h.push_back(1e9);
	sort(h.begin(), h.end());
	Rep0(i, h.size() - 1) if (h[i] != i) { sg[x] = i; break;}
	h.clear();
}

bool vis[N];
int main()
{
	int n, t;
	scanf("%d", &n);
	Rep(i, n) scanf("%d", &p[i]);
	
	t = 1;
	while (!vis[t]) vis[t] = true, t = p[t];
	//printf("%d\n", t);
	Rep(i, n) if (i != t) add_edge(p[i], i);
	
	dfs(t);
	
	if (sg[t] != sg[p[t]]) printf("POSSIBLE\n");
	else {
		int x = p[t];
		add_edge(p[t], t);
		int tmpt = sg[t];
		while (true) {
			RepG(i, x) h.push_back(sg[v]);
			h.push_back(1e9);
			sort(h.begin(), h.end());
			Rep0(i, h.size() - 1) if (h[i] != i) { sg[x] = i; break;}
			h.clear();
			if (x == t) break;
			x = p[x];
		}
		int tmp;
		RepG(i, x) h.push_back(p[t]);
		h.push_back(1e9);
		sort(h.begin(), h.end());
		Rep0(i, h.size() - 1) if (h[i] != i) { tmp = i; break;} 
		if (sg[t] == tmpt) printf("POSSIBLE\n");
		else printf("IMPOSSIBLE\n");
	}
	
	return 0;
}
### Prompt

Your challenge is to write 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 <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <ctime>

#define Rep(i, n) for (int i = 1; i <= n; i ++)
#define Rep0(i, n) for (int i = 0; i <= n; i ++)
#define RepG(i, x) for (int i = head[x]; i; i = edge[i].next)
#define v edge[i].to
#define mp(a, b) make_pair(a, b)

using namespace std;

const int N = 200010;

struct Edge{ int to, next;} edge[N];
int head[N], num, p[N];
void add_edge(int a, int b) { edge[++ num] = (Edge){b, head[a]}, head[a] = num;}
int sg[N];
vector<int> h;
void dfs(int x)
{
	//printf("%d\n", x);
	RepG(i, x) dfs(v);
	RepG(i, x) h.push_back(sg[v]);
	h.push_back(1e9);
	sort(h.begin(), h.end());
	Rep0(i, h.size() - 1) if (h[i] != i) { sg[x] = i; break;}
	h.clear();
}

bool vis[N];
int main()
{
	int n, t;
	scanf("%d", &n);
	Rep(i, n) scanf("%d", &p[i]);
	
	t = 1;
	while (!vis[t]) vis[t] = true, t = p[t];
	//printf("%d\n", t);
	Rep(i, n) if (i != t) add_edge(p[i], i);
	
	dfs(t);
	
	if (sg[t] != sg[p[t]]) printf("POSSIBLE\n");
	else {
		int x = p[t];
		add_edge(p[t], t);
		int tmpt = sg[t];
		while (true) {
			RepG(i, x) h.push_back(sg[v]);
			h.push_back(1e9);
			sort(h.begin(), h.end());
			Rep0(i, h.size() - 1) if (h[i] != i) { sg[x] = i; break;}
			h.clear();
			if (x == t) break;
			x = p[x];
		}
		int tmp;
		RepG(i, x) h.push_back(p[t]);
		h.push_back(1e9);
		sort(h.begin(), h.end());
		Rep0(i, h.size() - 1) if (h[i] != i) { tmp = i; break;} 
		if (sg[t] == tmpt) printf("POSSIBLE\n");
		else printf("IMPOSSIBLE\n");
	}
	
	return 0;
}
```