#include <bits/stdc++.h>

using namespace std;

int const N = 1234567;

int was[N], g[N], ng[N], p[N], cycle[N];

vector<int> edges[N];

int dfs(int v, int bad) {
  if (g[v] >= 0) return g[v];
  for (int to : edges[v]) {
    if (to == bad) continue;
    dfs(to, bad);
  }
  int children = (int) edges[v].size();
  for (int i = 0; i <= children; i++) was[i] = false;
  for (int to : edges[v]) {
    if (to == bad) continue;
    int got = dfs(to, bad);
    if (got <= children) was[got] = true;
  }
  int i = 0;
  while (was[i]) ++i;
  g[v] = i;
  return i;
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", p + i);
    --p[i];
    edges[p[i]].push_back(i);
    g[i] = -1;
  }
  int v = 0;
  for (int i = 0; i < n; i++) v = p[v];
  int cc = 0;
  int start = v;
  while (true) {
    cycle[cc++] = v;
    v = p[v];
    if (start == v) break;
  }
  dfs(cycle[0], cycle[cc - 1]);
  int gv = g[cycle[0]];
  for (int i = 0; i < n; i++) ng[i] = g[i];
  for (int value = gv; value <= gv + 1; value++) {
    for (int i = 0; i < n; i++) g[i] = ng[i];
    g[cycle[0]] = value;
    for (int i = 0; i < cc; i++) {
      int v = cycle[i];
      if (g[v] < 0) dfs(v, -1);
    }
    int last = cycle[cc - 1];
    if (value == gv && g[last] == gv) {
      continue;
    }
    if (value == gv + 1 && g[last] != gv) continue;
    puts("POSSIBLE");
    return 0;
  }
  puts("IMPOSSIBLE");
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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;

int const N = 1234567;

int was[N], g[N], ng[N], p[N], cycle[N];

vector<int> edges[N];

int dfs(int v, int bad) {
  if (g[v] >= 0) return g[v];
  for (int to : edges[v]) {
    if (to == bad) continue;
    dfs(to, bad);
  }
  int children = (int) edges[v].size();
  for (int i = 0; i <= children; i++) was[i] = false;
  for (int to : edges[v]) {
    if (to == bad) continue;
    int got = dfs(to, bad);
    if (got <= children) was[got] = true;
  }
  int i = 0;
  while (was[i]) ++i;
  g[v] = i;
  return i;
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", p + i);
    --p[i];
    edges[p[i]].push_back(i);
    g[i] = -1;
  }
  int v = 0;
  for (int i = 0; i < n; i++) v = p[v];
  int cc = 0;
  int start = v;
  while (true) {
    cycle[cc++] = v;
    v = p[v];
    if (start == v) break;
  }
  dfs(cycle[0], cycle[cc - 1]);
  int gv = g[cycle[0]];
  for (int i = 0; i < n; i++) ng[i] = g[i];
  for (int value = gv; value <= gv + 1; value++) {
    for (int i = 0; i < n; i++) g[i] = ng[i];
    g[cycle[0]] = value;
    for (int i = 0; i < cc; i++) {
      int v = cycle[i];
      if (g[v] < 0) dfs(v, -1);
    }
    int last = cycle[cc - 1];
    if (value == gv && g[last] == gv) {
      continue;
    }
    if (value == gv + 1 && g[last] != gv) continue;
    puts("POSSIBLE");
    return 0;
  }
  puts("IMPOSSIBLE");
}

```