/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 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 ≦ x < a_i) について、辺 (i, j) が存在し、かつ x = a_j を満たすような頂点 j が存在する。
この条件をみたすような割り当て方が存在するか判定してください。
制約
- 2 ≦ N ≦ 200,000
- 1 ≦ p_i ≦ N
- p_i \neq i
- グラフは弱連結
入力
入力は以下の形式で標準入力から与えられる。
N p_1 p_2 ... p_N
出力
うまく値を割り当てられるならば POSSIBLE、割り当てられないならば IMPOSSIBLE を出力する。
入力例 1
4 2 3 4 1
出力例 1
POSSIBLE
{a_i} = {0, 1, 0, 1} か、{a_i} = {1, 0, 1, 0} と割り当てることができます。
入力例 2
3 2 3 1
出力例 2
IMPOSSIBLE
入力例 3
4 2 3 1 1
出力例 3
POSSIBLE
{a_i} = {2, 0, 1, 0} と割り当てることができます。
入力例 4
6 4 5 6 5 6 4
出力例 4
IMPOSSIBLE
Score : 800 points
Problem Statement
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.
Sample Input 1
4 2 3 4 1
Sample Output 1
POSSIBLE
The assignment is possible: {a_i} = {0, 1, 0, 1} or {a_i} = {1, 0, 1, 0}.
Sample Input 2
3 2 3 1
Sample Output 2
IMPOSSIBLE
Sample Input 3
4 2 3 1 1
Sample Output 3
POSSIBLE
The assignment is possible: {a_i} = {2, 0, 1, 0}.
Sample Input 4
6 4 5 6 5 6 4
Sample Output 4
IMPOSSIBLE