分数: 800 点
问题陈述
有一个有向图 N 顶点和 N 边缘。顶点已编号 1, 2, ..., N.
该图有以下内容 N 边缘: (p_1, 1), (p_2, 2), ..., (p_N, N),并且该图是弱连通的。这里,来自顶点的一条边 u 到顶点 v 表示为 (u, v),弱连接图是如果每条边都是双向的则将连接的图。
我们想为此图中的每个顶点分配一个值,以便满足以下条件。在这里, a_i 是分配给顶点的值 i.
- 每个 a_i 是一个非负整数。
- 对于每条边 (i, j), a_i \neq a_j 成立。
- 对于每个 i 和每个整数 x(0 ≤ x < a_i),存在一个顶点 j 这样的边缘 (i, j) 存在并且 x = a_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