Problem Description

As is well known, Alice and Bob are good friends. Today, they have agreed to play a game together.

Initially, they each have a blank slip of paper. Subsequently, they will sequentially write $n$ positive integers within the range $[1, m]$ on their slips. After Alice finishes writing, Bob will start writing his slip after seeing what Alice has written.

Alice needs to ensure that the $i$-th number she writes is in the set $S_i$, and Bob needs to ensure that the $i$-th number he writes is in the set $T_i$. The problem guarantees that $1 \leq |S_i|, |T_i| \leq 2$.

Alice likes similarities, so she wants the number of positions where her numbers match Bob's to be as high as possible. Bob likes differences, so he wants his $n$ numbers $b_1, \ldots, b_n$ to be distinct. On this basis, Bob wants the number of positions where his numbers match Alice's to be as low as possible.

Let Alice's written numbers be $a_1, \ldots, a_n$ and Bob's written numbers be $b_1, \ldots, b_n$. Let $X$ be the number of indices $i$ such that $1 \leq i \leq n$ and $a_i = b_i$. Then:

• Alice wants to maximize $X$,
• Bob wants to minimize $X$ while ensuring that $b_1, \ldots, b_n$ are distinct.

You first want to know if Bob can ensure that his $n$ numbers are distinct. If he can, you want to know the value of $X under the optimal strategies of both parties.

Input Format

This problem contains multiple test cases.

The first line of input contains a positive integer $T$, indicating the number of test cases.

The following contains $T$ sets of data, each with the following format:

The first line contains two positive integers $n$ and $m$, indicating the number of numbers to be written on the slip and the range of values, respectively.

The next $n$ lines, the first integer on each line is $|S_i|$, indicating the number of elements in set $S_i$, followed by $|S_i|$ positive integers describing the elements of $S_i$.

The next $n$ lines, the first integer on each line is $|T_i|$, indicating the number of elements in set $T_i$, followed by $|T_i|$ positive integers describing the elements of $T_i$.

Output Format

For each set of test data, output one line: If Bob cannot ensure that his $n$ numbers are distinct, output -1; otherwise, output the value of $X under the optimal strategies of both parties.

Sample Input and Output

Input Sample #1

1
3 4
1 3
2 1 2
2 3 4
2 1 2
2 2 3
2 3 4

Output Sample #1

1

Input Sample #2

See attached file game/game2.in

Output Sample #2

See attached file game/game2.ans

Input Sample #3

See attached file game/game3.in

Output Sample #3

See attached file game/game3.ans

Input Sample #4

See attached file game/game4.in

Output Sample #4

See attached file game/game4.ans

Input Sample #5

See attached file game/game5.in

Output Sample #5

See attached file game/game5.ans

Input Sample #6

See attached file game/game6.in

Output Sample #6

See attached file game/game6.ans

Input Sample #7

See attached file game/game7.in

Output Sample #7

See attached file game/game7.ans

Input Sample #8

See attached file game/game8.in

Output Sample #8

See attached file game/game8.ans

Input Sample #9

See attached file game/game9.in

Output Sample #9

See attached file game/game9.ans

Notes/Hints

[Sample 1 Explanation]

In this sample, $S_1 = \{3\}, S_2 = T_1 = \{1, 2\}, S_3 = T_3 = \{3, 4\}, T_2 = \{2, 3\}$. Alice has 4 possible ways to fill in her numbers, listed as follows:

First: $a_1 = 3, a_2 = 1, a_3 = 3$.

Second: $a_1 = 3, a_2 = 1, a_3 = 4$.

Third: $a_1 = 3, a_2 = 2, a_3 = 3$.

Fourth: $a_1 = 3, a_2 = 2, a_3 = 4$.

Since Bob must ensure that his numbers are distinct, he has the following ways to fill in his numbers:

First: $b_1 = 1, b_2 = 2, b_3 = 3$.

Second: $b_1 = 2, b_2 = 3, b_3 = 4$.

Third: $b_1 = 1, b_2 = 2, b_3 = 4$.

Fourth: $b_1 = 1, b_2 = 3, b_3 = 4$.

If Alice chooses the first way, then to minimize $X$, Bob chooses the second way, resulting in $X = 0$.

If Alice chooses the second way, then to minimize $X$, Bob chooses the first way, resulting in $X = 0$.

If Alice chooses the third way, then to minimize $X$, Bob chooses the first way, resulting in $X = 0$.

If Alice chooses the fourth way, then no matter which way Bob chooses, $X$ is not less than 1.

Therefore, to maximize $X$, Alice will choose the fourth way.

[Subtasks]

The table lists $\sum n, \sum m$ which represent the sum of $n$ and $m$ across all test data in the same test point. $\sum n^2, \sum m^2, \sum n^3, \sum m^3$ are defined similarly.

Special Property A: For any $1 \leq i \leq n, S_i$ and $T_i$ are disjoint, i.e., $S_i \cap T_i = \emptyset$.

Special Property B: $n \geq 3$, and for any $1 \leq i < n, T_i = \{i, i+1\}$, and $T_n = \{n, 1\}$.

Special Property C: For any $1 \leq i \leq n, |S_i| = 1$.

Special Property D: For any $1 \leq i \leq n, S_i = T_i$.

[Hint]

Some test points have a large input size, we recommend using an efficient input method.

见题面 Input 部分

见题面 Output 部分