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 ≤ i ≤ 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 ≤ T ≤ 5$
$1 ≤ N ≤ 10^{5}$
$1 ≤ K ≤ 2$
$1 ≤ A_{i}, B_{i} ≤ N$

------ Subtasks ------
16 points : $K = 1$
84 points : No further constraints.

----- Sample Input 1 ------ 
	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 1 ------ 
	2
	2 8
----- explanation 1 ------ 
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$.

Difficulty: HARD

Starter code:

Solutions:
t = int(input())
mod = 1000000007
f = [1]
for i in range(1, 200002):
	f.append(i * f[i - 1] % mod)
while t > 0:
	t -= 1
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	p = []
	s = []
	for i in range(n + 1):
		p.append(i)
		s.append(1)

	def prnt(x):
		if p[x] != x:
			p[x] = prnt(p[x])
		return p[x]
	for i in range(1, n + 1):
		aa = prnt(a[i - 1])
		bb = prnt(b[i - 1])
		if aa != bb:
			p[bb] = aa
			s[aa] += s[bb]
	ans1 = 0
	ans2 = 1
	for i in range(1, n + 1):
		if prnt(i) == i and s[i] > 1:
			ans1 += s[i] - 1
			ans2 = ans2 * f[s[i]] % mod
	ans2 = ans2 * f[ans1] % mod
	if k == 1:
		print(ans1)
	if k == 2:
		print(ans1, ans2)