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

typedef long long ll;

ll N;
vector<ll> Parent;
vector<vector<ll>> Kids;
ll Root;
vector<ll> A;

void find_root() {
  vector<bool> Seen;
  Seen.resize(N);
  ll v;
  for (v = 0; !Seen[v]; v = Parent[v]) Seen[v] = true;
  Root = v;
}
ll dfs(ll v, ll mode) {
  unordered_set<ll> kids_as;
  for (ll w : Kids[v])
    if (w != Root) kids_as.insert(dfs(w, mode));
  vector<ll> a_candidates;
  for (ll x = 0; a_candidates.size() < 2; ++x)
    if (!kids_as.count(x)) a_candidates.push_back(x);
  return A[v] = v == Parent[Root] ? a_candidates[mode] : a_candidates[0];
}
bool check() {
  ll v = Parent[Root];
  unordered_set<ll> needed;
  for (ll x = 0; x < A[v]; ++x) needed.insert(x);
  for (ll w : Kids[v]) {
    if (A[v] == A[w]) return false;
    needed.erase(A[w]);
  }
  return needed.empty();
}
bool solve() {
  find_root();
  for (ll mode : {0, 1}) {
    A.resize(N, -1);
    dfs(Root, mode);
    if (check()) return true;
  }
  return false;
}
int main() {
  cin >> N;
  Parent.resize(N);
  Kids.resize(N);
  for (ll v = 0; v < N; ++v) {
    ll p;
    cin >> p;
    --p;
    Parent[v] = p;
    Kids[p].push_back(v);
  }
  cout << (solve() ? "POSSIBLE" : "IMPOSSIBLE") << endl;
  return 0;
}

### Prompt

Your task is to create 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>
using namespace std;

typedef long long ll;

ll N;
vector<ll> Parent;
vector<vector<ll>> Kids;
ll Root;
vector<ll> A;

void find_root() {
  vector<bool> Seen;
  Seen.resize(N);
  ll v;
  for (v = 0; !Seen[v]; v = Parent[v]) Seen[v] = true;
  Root = v;
}
ll dfs(ll v, ll mode) {
  unordered_set<ll> kids_as;
  for (ll w : Kids[v])
    if (w != Root) kids_as.insert(dfs(w, mode));
  vector<ll> a_candidates;
  for (ll x = 0; a_candidates.size() < 2; ++x)
    if (!kids_as.count(x)) a_candidates.push_back(x);
  return A[v] = v == Parent[Root] ? a_candidates[mode] : a_candidates[0];
}
bool check() {
  ll v = Parent[Root];
  unordered_set<ll> needed;
  for (ll x = 0; x < A[v]; ++x) needed.insert(x);
  for (ll w : Kids[v]) {
    if (A[v] == A[w]) return false;
    needed.erase(A[w]);
  }
  return needed.empty();
}
bool solve() {
  find_root();
  for (ll mode : {0, 1}) {
    A.resize(N, -1);
    dfs(Root, mode);
    if (check()) return true;
  }
  return false;
}
int main() {
  cin >> N;
  Parent.resize(N);
  Kids.resize(N);
  for (ll v = 0; v < N; ++v) {
    ll p;
    cin >> p;
    --p;
    Parent[v] = p;
    Kids[p].push_back(v);
  }
  cout << (solve() ? "POSSIBLE" : "IMPOSSIBLE") << endl;
  return 0;
}

```