#P13732. [ARC079F] Namori Grundy

    ID: 12934 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>CF2200提高+/省选-mex 计算基环树拆环树形 DP暴力枚举时间戳避免清空数组

[ARC079F] Namori Grundy

题目描述

高桥君有一个NN个点NN条边的有向图,点的的编号从11到NN

高桥君的图有NN条边,形如:(p1,1),(p2,2),...,(pN,N)(p_1,1),(p_2,2),...,(p_N,N),保证图是弱连通的。其中,(u,v)(u,v)表示一条从点uu到vv的单向边。“弱连通”是指:假如所有的边都是双向边,则图是连通图

高桥君为每个点设置了一个权值,aia_i表示点ii的权值。他希望图满足如下性质:

所有aia_i都是非负整数

对于每条边(i,j)(i,j),满足ai≠aja_i≠a_j

对于所有i,x(0≤x<ai)i,x(0\le x\lt a_i),存在一条边(i,j)(i,j)满足x=ajx=a_j

请你帮高桥君判断一下,这样图是否存在呢?

输入格式

NN

p1p_1 p2p_2 p3p_3 ...... pNp_N

输出格式

如果存在这样的图,输出POSSIBLE

否则输出IMPOSSIBLE

输入输出样例 #1

输入 #1

4
2 3 4 1

输出 #1

POSSIBLE

输入输出样例 #2

输入 #2

3
2 3 1

输出 #2

IMPOSSIBLE

输入输出样例 #3

输入 #3

4
2 3 1 1

输出 #3

POSSIBLE

输入输出样例 #4

输入 #4

6
4 5 6 5 6 4

输出 #4

IMPOSSIBLE

说明/提示

2≤N≤2000002 \leq N \leq 200000

1≤pi≤N1 \leq p_i \leq N

pi≠ip_i \ne i

保证给定的图是弱联通的