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