AT_agc018_f [AGC018F] Two Trees

[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

N/A

### 制約 - $ 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` になります。