题目描述

有两棵根树，每棵树有 $N$ 个顶点。每棵树的顶点编号从 $1$ 到 $N$。在第一棵树中，顶点 $i$ 的父节点是顶点 $A_i$。在这里，如果顶点 $i$ 是第一棵树的根节点，则 $A_i=-1$。在第二棵树中，顶点 $i$ 的父节点是顶点 $B_i$。在这里，如果顶点 $i$ 是第二棵树的根节点，则 $B_i=-1$。

Snuke 想要构建一个长度为 $N$ 的整数序列 $X_1, X_2, ..., X_N$，满足以下条件：

• 对于每棵树上的每个顶点，设其自身以及所有后代的索引为 $a_1, a_2, ..., a_k$。那么，必须满足 $|X_{a_1} + X_{a_2} + ... + X_{a_k}|=1$。

确定是否可以构建这样的序列。如果答案是肯定的，则找到一个满足条件的序列。

约束条件

• $1 \leq N \leq 10^5$
• 如果顶点 $i$ 不是第一棵树的根节点，则 $1 \leq A_i \leq N$。
• 如果顶点 $i$ 是第一棵树的根节点，则 $A_i = -1$。
• 如果顶点 $i$ 不是第二棵树的根节点，则 $1 \leq B_i \leq N$。
• 如果顶点 $i$ 是第二棵树的根节点，则 $B_i = -1$。
• 输入对应有效的根树。

输入

输入以以下格式从标准输入给出：

$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

例如，第一棵树中顶点 $3$ 和其后代的索引为 $3,1,2$。可以看出示例输出满足 $|X_3+X_1+X_2|=|(-1)+(1)+(-1)|=|-1|=1$。同样地，其他顶点也满足条件。

示例输入2

6
-1 5 1 5 1 3
6 5 5 3 -1 3

示例输出2

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