← 返回题目列表

AtCoder · agc018_f

F. 两棵树

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

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