#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <vector>

using namespace std;

#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " " <<
#define X first
#define Y second
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)

typedef pair<int, int> P;
typedef long long ll;

const int MAX = 1<<18;

vector <int> V[MAX];
int in[MAX], deg[MAX];
int n;
int p[MAX];
int ima[MAX];

int mex(int ind) {
  for (auto it : V[ind])
    if (p[it] != -1)      
      ima[p[it]] = 1;
  
  int ret=-1;
  REP(i, MAX) {
    if (!ima[i]) {
      ret = i;
      break;
    }
  }

  for (auto it : V[ind])
    if (p[it] != -1)
      ima[p[it]] = 0;
  
  return ret;  
}

void yup() {
  printf("POSSIBLE\n");
  exit(0);
}

void check() {
  REP(i, n)
    if (mex(i) != p[i])
      return;  
  yup();
}

int main()
{
  memset(p, -1, sizeof p);
  
  scanf("%d", &n);
  REP(i, n) {
    int x;
    scanf("%d", &x); x--;
    in[i] = x;
    V[x].push_back(i);
    deg[x]++;
  }

  queue <int> Q;
  REP(i, n)
    if (!deg[i])
      Q.push(i);

  for (; !Q.empty(); ) {
    int tmp = Q.front();
    Q.pop();
    
    p[tmp] = mex(tmp);
    deg[in[tmp]]--;
    if (!deg[in[tmp]])
      Q.push(in[tmp]);
  }

  int prvi=-1;
  REP(i, n)
    if (deg[i])
      prvi = i;

  assert(prvi != -1);

  int kamo = -1;
  for (auto it : V[prvi])
    if (deg[it])
      kamo = it;

  assert(kamo != -1);

  int poc = mex(prvi);
  p[prvi] = poc;
  for (int st=0, tmp=prvi; !st || tmp != prvi; st=1, tmp=in[tmp])
    p[tmp] = mex(tmp);
  
  check();

  p[kamo] = poc;
  for (int st=0, tmp=prvi; !st || tmp != prvi; st=1, tmp=in[tmp])
    p[tmp] = mex(tmp);

  check();

  printf("IMPOSSIBLE\n");  

  return 0;
}

### Prompt

Please create a solution in cpp 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 <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <vector>

using namespace std;

#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " " <<
#define X first
#define Y second
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)

typedef pair<int, int> P;
typedef long long ll;

const int MAX = 1<<18;

vector <int> V[MAX];
int in[MAX], deg[MAX];
int n;
int p[MAX];
int ima[MAX];

int mex(int ind) {
  for (auto it : V[ind])
    if (p[it] != -1)      
      ima[p[it]] = 1;
  
  int ret=-1;
  REP(i, MAX) {
    if (!ima[i]) {
      ret = i;
      break;
    }
  }

  for (auto it : V[ind])
    if (p[it] != -1)
      ima[p[it]] = 0;
  
  return ret;  
}

void yup() {
  printf("POSSIBLE\n");
  exit(0);
}

void check() {
  REP(i, n)
    if (mex(i) != p[i])
      return;  
  yup();
}

int main()
{
  memset(p, -1, sizeof p);
  
  scanf("%d", &n);
  REP(i, n) {
    int x;
    scanf("%d", &x); x--;
    in[i] = x;
    V[x].push_back(i);
    deg[x]++;
  }

  queue <int> Q;
  REP(i, n)
    if (!deg[i])
      Q.push(i);

  for (; !Q.empty(); ) {
    int tmp = Q.front();
    Q.pop();
    
    p[tmp] = mex(tmp);
    deg[in[tmp]]--;
    if (!deg[in[tmp]])
      Q.push(in[tmp]);
  }

  int prvi=-1;
  REP(i, n)
    if (deg[i])
      prvi = i;

  assert(prvi != -1);

  int kamo = -1;
  for (auto it : V[prvi])
    if (deg[it])
      kamo = it;

  assert(kamo != -1);

  int poc = mex(prvi);
  p[prvi] = poc;
  for (int st=0, tmp=prvi; !st || tmp != prvi; st=1, tmp=in[tmp])
    p[tmp] = mex(tmp);
  
  check();

  p[kamo] = poc;
  for (int st=0, tmp=prvi; !st || tmp != prvi; st=1, tmp=in[tmp])
    p[tmp] = mex(tmp);

  check();

  printf("IMPOSSIBLE\n");  

  return 0;
}

```