配点 : $800$ 点

問題文

$N$ 頂点 $N$ 辺の有向グラフを考えます。頂点には番号 $1, 2, ..., N$ が振られているものとします。

このグラフは $(p_1, 1), (p_2, 2), ..., (p_N, N)$ の $N$ 本の辺からなり、弱連結です。 なお、この問題では頂点 $u$ から頂点 $v$ へ入り込む辺を $(u, v)$ と表します。また、弱連結とは、辺を無向辺として見るとグラフ全体が連結になっているという意味です。

このグラフの頂点に、以下の条件を満たすように値を割り当てたいです。頂点 $i$ に割り当てる値を $a_i$ とします。

• $a_i$ は、$0$ 以上の非負整数である。
• すべての辺 $(i, j)$ について、$a_i \neq a_j$ である。
• すべての頂点 $i$ と整数 $x(0 \leq x < a_i)$ について、辺 $(i, j)$ が存在し、かつ $x = a_j$ を満たすような頂点 $j$ が存在する。

この条件をみたすような割り当て方が存在するか判定してください。

制約

• $2 \leq N \leq 200,000$
• $1 \leq p_i \leq N$
• $p_i \neq i$
• グラフは弱連結

入力

入力は以下の形式で標準入力から与えられる。

$N$

$p_1$ $p_2$ ... $p_N$

出力

うまく値を割り当てられるならば POSSIBLE、割り当てられないならば IMPOSSIBLE を出力する。

4
2 3 4 1

POSSIBLE

{$a_i$} = {$0, 1, 0, 1$} か、{$a_i$} $=$ {$1, 0, 1, 0$} と割り当てることができます。

3
2 3 1

IMPOSSIBLE

4
2 3 1 1

POSSIBLE

{$a_i$} $=$ {$2, 0, 1, 0$} と割り当てることができます。

6
4 5 6 5 6 4

IMPOSSIBLE