配点 : $1700$ 点

問題文

$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$ つ求めてください。

制約

• $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な根付き木である。

入力

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

$N$

$A_1$ $A_2$ $..$ $A_N$

$B_1$ $B_2$ $..$ $B_N$

出力

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

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

POSSIBLE
1 -1 -1 3 -1

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

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

IMPOSSIBLE

この例では、どうやっても条件を満たす整数列は作れません。 よって、この例の答えは 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