AT_arc189_c [ARC189C] Balls and Boxes

[problemUrl]: https://atcoder.jp/contests/arc189/tasks/arc189_c $ N $ 個の箱があります。 $ i\ =\ 1,\ 2,\ \ldots,\ N $ について、$ i $ 番目の箱には $ A_i $ 個の赤いボールと $ B_i $ 個の青いボールが入っています。 また、数列 $ (1,\ 2,\ \ldots,\ N) $ を並べ替えた $ 2 $ つの順列 $ P\ =\ (P_1,\ P_2,\ \ldots,\ P_N) $ と $ Q\ =\ (Q_1,\ Q_2,\ \ldots,\ Q_N) $ が与えられます。 高橋君は、下記の操作を好きな回数（ $ 0 $ 回でも良い）だけ繰り返すことができます。 - $ 1\ \leq\ i\ \leq\ N $を満たす整数 $ i $ を選び、$ i $ 番目の箱に入っているすべてのボールを箱から取り出して手に持つ。 - 手に持っているすべての赤いボールを $ P_i $ 番目の箱に入れる。 - 手に持っているすべての青いボールを $ Q_i $ 番目の箱に入れる。 高橋君の目標は、上記の操作の繰り返しによって、$ X $ 番目の箱以外にボールが入っていない状態にすることです。 この目標を達成することが可能かどうかを判定し、可能な場合はそのために行う操作回数の最小値を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ X $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ B_1 $ $ B_2 $ $ \ldots $ $ B_N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $ $ Q_1 $ $ Q_2 $ $ \ldots $ $ Q_N $

高橋君が $ X $ 番目の箱以外にボールが入っていない状態にすることが不可能な場合は `-1` を、 可能な場合はそのために行う操作回数の最小値を出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 0\ \leq\ A_i,\ B_i\ \leq\ 1 $ - $ 1\ \leq\ P_i,\ Q_i\ \leq\ N $ - $ P,Q $ はそれぞれ $ (1,\ 2,\ \ldots,\ N) $ の順列 - $ 1\ \leq\ X\ \leq\ N $ - 入力はすべて整数 ### Sample Explanation 1 各箱に入っている赤いボールと青いボールの個数はそれぞれ $ A\ =\ (0,\ 1,\ 0,\ 1,\ 0),\ B\ =\ (0,\ 0,\ 1,\ 0,\ 1) $ で与えられています。 下記の手順を考えます。 - まず、$ 5 $ 番目の箱に対して操作を行う。その結果、$ A\ =\ (0,\ 1,\ 0,\ 1,\ 0),\ B\ =\ (1,\ 0,\ 1,\ 0,\ 0) $ となる。 - 次に、$ 2 $ 番目の箱に対して操作を行う。その結果、$ A\ =\ (1,\ 0,\ 0,\ 1,\ 0),\ B\ =\ (1,\ 0,\ 1,\ 0,\ 0) $ となる。 - さらに、$ 1 $ 番目の箱に対して操作を行う。その結果、$ A\ =\ (0,\ 0,\ 0,\ 2,\ 0),\ B\ =\ (0,\ 0,\ 2,\ 0,\ 0) $ となる。 - 最後に、$ 4 $ 番目の箱に対して操作を行う。その結果、$ A\ =\ (0,\ 0,\ 2,\ 0,\ 0),\ B\ =\ (0,\ 0,\ 2,\ 0,\ 0) $ となる。 上記の $ 4 $ 回の操作によって、$ X\ =\ 3 $ 番目の箱以外にボールが入っていない状態にすることができます。 これが考えられる最小の操作回数です。 ### Sample Explanation 2 どの箱にもボールが入っていません。 よって、はじめから $ X\ =\ 3 $ 番目の箱以外にボールが入っていない状態であるので、必要な操作回数は $ 0 $ 回です。 ### Sample Explanation 3 どのような手順で操作を行っても、$ X\ =\ 2 $ 番目の箱以外にボールが入っていない状態にすることはできません。