分数: 1700 点
问题陈述
有两棵有根树,每棵树都有 N 顶点。 每棵树的顶点都有编号 1 通过 N。 在第一棵树中,Vertex 的父级 i 是顶点 A_i。 在这里, A_i=-1 如果顶点 i 是第一棵树的根。 在第二棵树中,Vertex 的父级 i 是顶点 B_i。 在这里, B_i=-1 如果顶点 i 是第二棵树的根。
Snuke想要构造一个长度为整数的序列 N, X_1 , X_2 , ... , X_N,满足以下条件:
- 对于每棵树上的每个顶点,令其后代(包括其自身)的索引为 a_1 , a_2 , ..., a_k。然后, abs(X_{a_1} + X_{a_2} + ... + X_{a_k})=1 成立。
确定是否可以构造这样的序列。如果答案可能,请找到一个这样的序列。
约束
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq N,如果顶点 i 不是第一棵树的根。
- A_i = -1,如果顶点 i 是第一棵树的根。
- 1 \leq B_i \leq N,如果顶点 i 不是第二棵树中的根。
- B_i = -1,如果顶点 i 是第二棵树的根。
- 输入对应于有效的有根树。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 .. A_N B_1 B_2 .. B_N
输出
如果无法构造满足条件的整数序列,则打印 IMPOSSIBLE。
如果可以的话,打印 POSSIBLE 在第一行。
然后,在第二行中打印 X_1 , X_2 , ... , X_N,满足条件的整数序列。
示例输入 1
5 3 3 4 -1 4 4 4 1 -1 1
示例输出 1
POSSIBLE 1 -1 -1 3 -1
例如,Vertex 的后代的索引 第一棵树(包括其自身)的 3 是 3,1,2。 可以看出样本输出保持 abs(X_3+X_1+X_2)=abs((-1)+(1)+(-1))=abs(-1)=1。 同样,其他顶点也满足该条件。
示例输入 2
6 -1 5 1 5 1 3 6 5 5 3 -1 3
示例输出 2
IMPOSSIBLE
在这种情况下,构造满足条件的序列是 IMPOSSIBLE.
示例输入 3
8 2 7 1 2 2 1 -1 4 4 -1 4 7 4 4 2 4
示例输出 3
POSSIBLE 1 2 -1 0 -1 1 0 -1