All submissions for this problem are available.You are given two arrays $A$ = $A_1, A_2, \ldots, A_N$ and $B$ = $B_1, B_2, \ldots, B_N$. We want to make these two arrays identical. That is, for each $1 \leq i \leq N$, we want to make $A_i$ = $B_i$. To do this, we are allowed to make many operations of the following type: In a single operation, we choose two integers $x$ and $y$, and replace all the occurrences of $x$ in both the arrays with $y$. This operation is denoted by $(x, y)$. Notice that regardless of the number of characters replaced, it will still be counted as a single operation. A sequence of operations $((x_1, y_1), (x_2, y_2), \ldots, (x_m, y_m))$ is said to be optimal, if after performing these operations in the given order, both arrays $A$ and $B$ are identical, and there is no sequence with fewer operations which can achieve the same. You will also be given an integer $K$ which will either be $1$ or $2$. If $K = 1$, you need to output the minimum number of operations needed to make the two arrays identical. If $K = 2$, in addition to the minimum number of operations, you should also output the number of different optimal sequences. As this number could be huge, output it modulo $10^9 + 7$. ###Input: - The first line of the input contains a single integer, $T$, which is the number of testcases. The description of each testcase follows. - The first line of each testcase contains two integers: $N$, and $K$. - The next line contains $N$ integers: $A_1, A_2, \ldots, A_N$. - The next line contains $N$ integers: $B_1, B_2, \ldots, B_N$. ###Output: - You need to output a single line for each testcase. - If $K = 1$, then that corresponding line should contain a single integer, which is the minimum number of operations needed. - If $K = 2$, then that corresponding line should contain two integers, the minimum number of operations needed and the number of optimal sequences modulo $10^9 + 7$. ###Constraints - $1 \leq T \leq 5$ - $1 \leq N \leq 10^5$ - $1 \leq K \leq 2$ - $1 \leq A_i, B_i \leq N$ ###Subtasks - 16 points : $K = 1$ - 84 points : No further constraints. ###Sample Input: 2 5 1 2 1 1 3 5 1 2 2 4 5 5 2 2 1 1 3 5 1 2 2 4 5 ###Sample Output: 2 2 8 ###Explanation: Testcase 1: The arrays are initially $(2, 1, 1, 3, 5)$ and $(1, 2, 2, 4, 5)$. Consider the sequence of operations $((1, 2), (3, 4))$. In the first operation all the $1$s are converted into $2$s. So, the arrays will now be $(2, 2, 2, 3, 5)$ and $(2, 2, 2, 4, 5)$. In the second operation all the $3$s are converted into $4$s. So, the arrays will now be $(2, 2, 2, 4, 5)$ and $(2, 2, 2, 4, 5)$. We have made the two arrays identical in two operations, and you can check that you cannot do better. Hence the output is $2$. Testcase 2: The arrays are the same, and hence the first integer is the same. Now we need to also find the number of optimal sequences. They are listed below: - $((1, 2), (3, 4))$ - $((1, 2), (4, 3))$ - $((2, 1), (3, 4))$ - $((2, 1), (4, 3))$ - $((3, 4), (1, 2))$ - $((3, 4), (2, 1))$ - $((4, 3), (1, 2))$ - $((4, 3), (2, 1))$ Since there are eight optimal sequences, the second integer is $8$.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, LISP sbcl, LISP clisp, SCM guile, ERL, TCL, kotlin, TEXT, SCM chicken, FS|
Fetching successful submissions