#pragma GCC optimize(2)
#pragma G++ optimize(2)
#include<bits/stdc++.h>
#define si(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define sd(a) scanf("%lf",&a)
#define ss(a) scanf("%s",a)
#define ms(a) memset(a,0,sizeof(a))
#define repi(i,a,b) for(register int i=a;i<=b;++i)
#define repd(i,a,b) for(register int i=a;i>=b;--i)
#define reps(s) for(int i=head[s],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
#define ce(i,r) i==r?'\n':' '
#define pb push_back 
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define pr(x) cout<<#x<<": "<<x<<endl
using namespace std;
typedef long long ll;
const int MAX_N=2e5+5;
const int MAX_E=2e5+5;
struct Edge{int to,nxt;}e[MAX_E<<1];
int head[MAX_N],tote;
void add_edge(int u,int v){e[++tote].to=v,e[tote].nxt=head[u];head[u]=tote;}
int root,fa[MAX_N];
bool vis[MAX_N],in_loop[MAX_N];
void find_root(int s)
{
	vis[s]=true;
	if(vis[fa[s]]) root=s;
	else find_root(fa[s]);
}
int loop[MAX_N],lpc=0;
void get_loop()
{
	find_root(1);
	loop[++lpc]=root,in_loop[root]=true;
	int now=fa[root];
	while(now!=root) loop[++lpc]=now,in_loop[now]=true,now=fa[now];
	loop[lpc+1]=root;
}
int val[MAX_N];
bool mex[MAX_N];
void dfs(int u)
{
	reps(u)if(!in_loop[v]) dfs(v);
	reps(u)if(!in_loop[v]) mex[val[v]]=true;
	while(mex[val[u]]) val[u]++;
	reps(u)if(!in_loop[v]) mex[val[v]]=false;
}
void init(int n)
{
	repi(i,0,n) head[i]=val[i]=mex[i]=0;
	tote=0;
}
int main()
{	
	int n; si(n);
	repi(i,1,n) si(fa[i]),add_edge(fa[i],i); 
	get_loop();
	repi(i,1,lpc) dfs(loop[i]);
	bool flag=false;
	repi(i,2,lpc)if(val[loop[i]]!=val[loop[i-1]]){ flag=true; break; }
	if(!flag&&(lpc&1)) puts("IMPOSSIBLE");
	else puts("POSSIBLE");
	return 0;
}
### Prompt

Create a solution in CPP for 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
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#include<bits/stdc++.h>
#define si(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define sd(a) scanf("%lf",&a)
#define ss(a) scanf("%s",a)
#define ms(a) memset(a,0,sizeof(a))
#define repi(i,a,b) for(register int i=a;i<=b;++i)
#define repd(i,a,b) for(register int i=a;i>=b;--i)
#define reps(s) for(int i=head[s],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
#define ce(i,r) i==r?'\n':' '
#define pb push_back 
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define pr(x) cout<<#x<<": "<<x<<endl
using namespace std;
typedef long long ll;
const int MAX_N=2e5+5;
const int MAX_E=2e5+5;
struct Edge{int to,nxt;}e[MAX_E<<1];
int head[MAX_N],tote;
void add_edge(int u,int v){e[++tote].to=v,e[tote].nxt=head[u];head[u]=tote;}
int root,fa[MAX_N];
bool vis[MAX_N],in_loop[MAX_N];
void find_root(int s)
{
	vis[s]=true;
	if(vis[fa[s]]) root=s;
	else find_root(fa[s]);
}
int loop[MAX_N],lpc=0;
void get_loop()
{
	find_root(1);
	loop[++lpc]=root,in_loop[root]=true;
	int now=fa[root];
	while(now!=root) loop[++lpc]=now,in_loop[now]=true,now=fa[now];
	loop[lpc+1]=root;
}
int val[MAX_N];
bool mex[MAX_N];
void dfs(int u)
{
	reps(u)if(!in_loop[v]) dfs(v);
	reps(u)if(!in_loop[v]) mex[val[v]]=true;
	while(mex[val[u]]) val[u]++;
	reps(u)if(!in_loop[v]) mex[val[v]]=false;
}
void init(int n)
{
	repi(i,0,n) head[i]=val[i]=mex[i]=0;
	tote=0;
}
int main()
{	
	int n; si(n);
	repi(i,1,n) si(fa[i]),add_edge(fa[i],i); 
	get_loop();
	repi(i,1,lpc) dfs(loop[i]);
	bool flag=false;
	repi(i,2,lpc)if(val[loop[i]]!=val[loop[i-1]]){ flag=true; break; }
	if(!flag&&(lpc&1)) puts("IMPOSSIBLE");
	else puts("POSSIBLE");
	return 0;
}
```