[AGC018F] Two Trees

给定两棵都是$N$个节点的有根树$A,B$，节点均从$1..N$标号。 我们需要给每个标号定一个权值，使在两棵树上均满足任意节点子树权值和为$1$或$-1$ 输出任意一种解，需要判断无解 $N\leqslant 100000$

[problemUrl]: https://atcoder.jp/contests/agc018/tasks/agc018_f $ 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 $ を空白区切りで出力せよ。

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` になります。