← 返回题目列表

AtCoder · arc079_d

F. 纳莫里·格伦迪

中文机器翻译题面 查看原题

分数: 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