题目描述

$N$ 頂点からなる根付き木が $2$ つあります。 どちらの木の頂点も、それぞれ $1$ から $N$ の番号がついています。 $1$ つめの木の 頂点 $i$ の親は $A_i$ です。 なお、頂点 $i$ が根のときは、$A_i=-1$です。 $2$ つめの木の 頂点 $i$ の親は $B_i$ です。 なお、頂点 $i$ が根のときは、$B_i=-1$です。

すぬけ君は、長さ $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$ つ求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $A_1$ $A_2$ $..$ $A_N$ $B_1$ $B_2$ $..$ $B_N$

输出格式

条件を満たす整数列を作ることができない場合は、IMPOSSIBLE と出力せよ。 作ることができる場合は、まず $1$ 行目に、POSSIBLE と出力せよ。 続いて、$2$ 行目には条件を満たす整数列 $X_1$ , $X_2$ , $...$ , $X_N$ を空白区切りで出力せよ。

题目大意

给定两棵都是$N$个节点的有根树$A,B$，节点均从$1..N$标号。

我们需要给每个标号定一个权值，使在两棵树上均满足任意节点子树权值和为$1$或$-1$

输出任意一种解，需要判断无解 $N\leqslant 100000$

5
3 3 4 -1 4
4 4 1 -1 1

POSSIBLE
1 -1 -1 3 -1

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

IMPOSSIBLE

8
2 7 1 2 2 1 -1 4
4 -1 4 7 4 4 2 4

POSSIBLE
1 2 -1 0 -1 1 0 -1

提示

制約

• $1\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ A_i\ \leq\ N$ (頂点 $i$ が $1$ つ目の木の根でないとき)
• $A_i\ =\ -1$ (頂点 $i$ が $1$ つ目の木の根のとき)
• $1\ \leq\ B_i\ \leq\ N$ (頂点 $i$ が $2$ つ目の木の根でないとき)
• $B_i\ =\ -1$ (頂点 $i$ が $2$ つ目の木の根のとき)
• 入力はvalidな根付き木である。

Sample Explanation 1

例えば、$1$ つ目の木の頂点 $3$ について見てみると、その頂点と子孫の頂点の番号は、$3,1,2$ となっています。 出力例のように整数列を設定すると、$abs(X_3+X_1+X_2)=abs((-1)+(1)+(-1))=abs(-1)=1$ となっており、問題ありません。 他の頂点についても同じように確かめると、確かに出力例の整数列は条件を満たしています。

Sample Explanation 2

この例では、どうやっても条件を満たす整数列は作れません。 よって、この例の答えは IMPOSSIBLE になります。