AT_arc079_d [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$
保证给定的图是弱联通的