#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int grn(vector<vector<int>> &e, vector<int> &grundy, int now){
	if(0 <= grundy[now]) return grundy[now];
	vector<int> v;
	for(int next:e[now]) v.emplace_back(grn(e, grundy, next));
	sort(v.begin(), v.end());
	int ret = 0;
	for(int p:v){
		if(p < ret) continue;
		if(ret == p){
			ret++;
			continue;
		}
		break;
	}
	return grundy[now] = ret;
}

bool check(vector<vector<int>> &e, vector<int> &grundy, int i){
	int c = grundy[i];
	set<int> s;
	for(int next:e[i]){
		int t = grundy[next];
		if(t < c) s.insert(t);
		if(t == c) return false;
	}
	return s.size() == c;
}

int main(){
	int n;
	cin >> n;
	vector<int> f(n);
	vector<vector<int>> e(n);
	for(int i = 0; i < n; i++){
		int p;
		cin >> p;
		e[--p].emplace_back(i);
		f[i] = p;
	}
	vector<int> loop, used(n, -1);
	int loop_start = 0;
	{
		int puni = 0;
		while(used[puni] < 0){
			used[puni] = loop.size();
			loop.emplace_back(puni);
			puni = f[puni];
		}
		loop_start = used[puni];
	}
	int min_deg = n + 1, min_vert = 0;
	for(int i = loop_start; i < loop.size(); i++){
		int v = loop[i];
		int deg = e[v].size();
		if(deg < min_deg){
			min_deg = deg;
			min_vert = v;
		}
	}
	vector<int> grundy(n);
	for(int cand = 0; cand <= min_deg; cand++){
		for(int i = 0; i < n; i++){
			grundy[i] = i == min_vert ? cand : -1;
		}
		for(int i = 0; i < n; i++) if(i != min_vert){
			grn(e, grundy, i);
		}
		if(check(e, grundy, min_vert)){
			cout << "POSSIBLE" << endl;
			return 0;
		}
	}
	cout << "IMPOSSIBLE" << endl;
}
### Prompt

Generate 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 <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int grn(vector<vector<int>> &e, vector<int> &grundy, int now){
	if(0 <= grundy[now]) return grundy[now];
	vector<int> v;
	for(int next:e[now]) v.emplace_back(grn(e, grundy, next));
	sort(v.begin(), v.end());
	int ret = 0;
	for(int p:v){
		if(p < ret) continue;
		if(ret == p){
			ret++;
			continue;
		}
		break;
	}
	return grundy[now] = ret;
}

bool check(vector<vector<int>> &e, vector<int> &grundy, int i){
	int c = grundy[i];
	set<int> s;
	for(int next:e[i]){
		int t = grundy[next];
		if(t < c) s.insert(t);
		if(t == c) return false;
	}
	return s.size() == c;
}

int main(){
	int n;
	cin >> n;
	vector<int> f(n);
	vector<vector<int>> e(n);
	for(int i = 0; i < n; i++){
		int p;
		cin >> p;
		e[--p].emplace_back(i);
		f[i] = p;
	}
	vector<int> loop, used(n, -1);
	int loop_start = 0;
	{
		int puni = 0;
		while(used[puni] < 0){
			used[puni] = loop.size();
			loop.emplace_back(puni);
			puni = f[puni];
		}
		loop_start = used[puni];
	}
	int min_deg = n + 1, min_vert = 0;
	for(int i = loop_start; i < loop.size(); i++){
		int v = loop[i];
		int deg = e[v].size();
		if(deg < min_deg){
			min_deg = deg;
			min_vert = v;
		}
	}
	vector<int> grundy(n);
	for(int cand = 0; cand <= min_deg; cand++){
		for(int i = 0; i < n; i++){
			grundy[i] = i == min_vert ? cand : -1;
		}
		for(int i = 0; i < n; i++) if(i != min_vert){
			grn(e, grundy, i);
		}
		if(check(e, grundy, min_vert)){
			cout << "POSSIBLE" << endl;
			return 0;
		}
	}
	cout << "IMPOSSIBLE" << endl;
}
```