[ARC079F] Namori Grundy

# 题目描述 高桥君有一个$N$个点$N$条边的有向图，点的的编号从$1$到$N$ 高桥君的图有$N$条边，形如：$(p_1,1),(p_2,2),...,(p_N,N)$，保证图是弱连通的。其中，$(u,v)$表示一条从点$u$到$v$的单向边。“弱连通”是指：假如所有的边都是双向边，则图是连通图 高桥君为每个点设置了一个权值，$a_i$表示点$i$的权值。他希望图满足如下性质： 所有$a_i$都是非负整数 对于每条边$(i,j)$，满足$a_i≠a_j$ 对于所有$i,x(0\le x\lt a_i)$，存在一条边$(i,j)$满足$x=a_j$ 请你帮高桥君判断一下，这样图是否存在呢？ # 输入格式 $N$ $p_1$ $p_2$ $p_3$ $...$ $p_N$ # 输出格式 如果存在这样的图，输出```POSSIBLE``` 否则输出```IMPOSSIBLE``` # 说明 $2 \leq N \leq 200000$ $1 \leq p_i \leq N$ $p_i \ne i$ 保证给定的图是弱联通的

[problemUrl]: https://atcoder.jp/contests/arc079/tasks/arc079_d $ 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\ ≦\ x\ <\ a_i) $ について、辺 $ (i,\ j) $ が存在し、かつ $ x\ =\ a_j $ を満たすような頂点 $ j $ が存在する。 この条件をみたすような割り当て方が存在するか判定してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ p_1 $ $ p_2 $ ... $ p_N $

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

4
2 3 4 1

POSSIBLE

3
2 3 1

IMPOSSIBLE

4
2 3 1 1

POSSIBLE

6
4 5 6 5 6 4

IMPOSSIBLE

### 制約 - $ 2\ ≦\ N\ ≦\ 200,000 $ - $ 1\ ≦\ p_i\ ≦\ N $ - $ p_i\ \neq\ i $ - グラフは弱連結 ### Sample Explanation 1 {$ a_i $} = {$ 0,\ 1,\ 0,\ 1 $} か、{$ a_i $} $ = $ {$ 1,\ 0,\ 1,\ 0 $} と割り当てることができます。 ### Sample Explanation 3 {$ a_i $} $ = $ {$ 2,\ 0,\ 1,\ 0 $} と割り当てることができます。