{"problem":{"name":"Balls and Boxes","description":{"content":"There are $N$ boxes. For $i = 1, 2, \\ldots, N$, the $i$\\-th box contains $A_i$ red balls and $B_i$ blue balls. You are also given two permutations $P = (P_1, P_2, \\ldots, P_N)$ and $Q = (Q_1, Q_2, \\ld","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc189_c"},"statements":[{"statement_type":"Markdown","content":"There are $N$ boxes. For $i = 1, 2, \\ldots, N$, the $i$\\-th box contains $A_i$ red balls and $B_i$ blue balls.\nYou are also given two permutations $P = (P_1, P_2, \\ldots, P_N)$ and $Q = (Q_1, Q_2, \\ldots, Q_N)$ of $(1, 2, \\ldots, N)$.\nTakahashi can repeat the following operation any number of times, possibly zero:\n\n*   Choose an integer $1 \\leq i \\leq N$, and take all the balls from the $i$\\-th box into his hand.\n*   Put all the red balls in his hand into the $P_i$\\-th box.\n*   Put all the blue balls in his hand into the $Q_i$\\-th box.\n\nHis goal is to make a state where all boxes other than the $X$\\-th box contain no balls by repeating the above operations. Determine whether it is possible to achieve his goal, and if possible, print the minimum number of operations needed to achieve it.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $0 \\leq A_i, B_i \\leq 1$\n*   $1 \\leq P_i, Q_i \\leq N$\n*   $P$ and $Q$ are permutations of $(1, 2, \\ldots, N)$.\n*   $1 \\leq X \\leq N$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $X$\n$A_1$ $A_2$ $\\ldots$ $A_N$\n$B_1$ $B_2$ $\\ldots$ $B_N$\n$P_1$ $P_2$ $\\ldots$ $P_N$\n$Q_1$ $Q_2$ $\\ldots$ $Q_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc189_c","tags":[],"sample_group":[["5 3\n0 1 0 1 0\n0 0 1 0 1\n4 1 2 3 5\n3 4 5 2 1","4\n\nThe numbers of red and blue balls in each box are $A = (0, 1, 0, 1, 0)$ and $B = (0, 0, 1, 0, 1)$, respectively. Consider the following steps:\n\n*   First, perform the operation on the 5th box. As a result, $A = (0, 1, 0, 1, 0)$, $B = (1, 0, 1, 0, 0)$.\n*   Next, perform the operation on the 2nd box. As a result, $A = (1, 0, 0, 1, 0)$, $B = (1, 0, 1, 0, 0)$.\n*   Then, perform the operation on the 1st box. As a result, $A = (0, 0, 0, 2, 0)$, $B = (0, 0, 2, 0, 0)$.\n*   Finally, perform the operation on the 4th box. As a result, $A = (0, 0, 2, 0, 0)$, $B = (0, 0, 2, 0, 0)$.\n\nThese four operations achieve a state where all boxes other than the $X$\\-th (3rd) box contain no balls. This is the minimum number of operations possible."],["5 3\n0 0 0 0 0\n0 0 0 0 0\n4 1 2 3 5\n3 4 5 2 1","0\n\nThere are no balls in any boxes. Thus, the state where all boxes other than the $X$\\-th (3rd) box contain no balls is already achieved, so the required number of operations is $0$."],["2 2\n1 1\n1 1\n1 2\n1 2","\\-1\n\nThere is no way to perform the operation to achieve a state where all boxes other than the $X$\\-th (2nd) box contain no balls."],["10 10\n0 0 0 0 0 0 1 0 1 0\n0 0 0 0 1 1 0 0 1 0\n1 4 9 5 8 2 3 6 10 7\n7 4 9 10 6 3 1 2 8 5","8"]],"created_at":"2026-03-03 11:01:14"}}