#include<bits/stdc++.h>
#define N 400005
using namespace std;
int n,p[N],fa[N];
int head[N],ver[N],nxt[N],vis[N],tot;
void add(int a,int b)
{
    tot++;nxt[tot]=head[a];head[a]=tot;ver[tot]=b;return ;
}
int find(int x)
{
    if(vis[x])return x;
    vis[x]=1;
    return find(p[x]);
}
vector<int>v;
int tim;
int f[N],c[N];
void dfs(int x)
{
    for(int i=head[x];i;i=nxt[i])if(!vis[ver[i]])dfs(ver[i]);
    tim++;
    for(int i=head[x];i;i=nxt[i])if(!vis[ver[i]])c[f[ver[i]]]=tim;
    for(int i=0;;i++)
    {
        f[x]=i;
        if(c[i]!=tim)break;
    }
    return ;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&p[i]);add(p[i],i);fa[p[i]]=i;
    }
    int x=find(1);
    memset(vis,0,sizeof(vis));
    do{
        v.push_back(x);
        vis[x]=1;
        x=p[x];
    }while(x!=v[0]);
    if (!(v.size()&1))  {puts("POSSIBLE");  return 0;}
    for(int i=0;i<v.size();i++)dfs(v[i]);
    v.push_back(x);
    for(int i=0;i<v.size()-1;i++)
        if(f[v[i]]!=f[v[i+1]]){puts("POSSIBLE");return 0;}
    puts("IMPOSSIBLE");
    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<bits/stdc++.h>
#define N 400005
using namespace std;
int n,p[N],fa[N];
int head[N],ver[N],nxt[N],vis[N],tot;
void add(int a,int b)
{
    tot++;nxt[tot]=head[a];head[a]=tot;ver[tot]=b;return ;
}
int find(int x)
{
    if(vis[x])return x;
    vis[x]=1;
    return find(p[x]);
}
vector<int>v;
int tim;
int f[N],c[N];
void dfs(int x)
{
    for(int i=head[x];i;i=nxt[i])if(!vis[ver[i]])dfs(ver[i]);
    tim++;
    for(int i=head[x];i;i=nxt[i])if(!vis[ver[i]])c[f[ver[i]]]=tim;
    for(int i=0;;i++)
    {
        f[x]=i;
        if(c[i]!=tim)break;
    }
    return ;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&p[i]);add(p[i],i);fa[p[i]]=i;
    }
    int x=find(1);
    memset(vis,0,sizeof(vis));
    do{
        v.push_back(x);
        vis[x]=1;
        x=p[x];
    }while(x!=v[0]);
    if (!(v.size()&1))  {puts("POSSIBLE");  return 0;}
    for(int i=0;i<v.size();i++)dfs(v[i]);
    v.push_back(x);
    for(int i=0;i<v.size()-1;i++)
        if(f[v[i]]!=f[v[i+1]]){puts("POSSIBLE");return 0;}
    puts("IMPOSSIBLE");
    return 0;
}

```