Problem Description

As everyone knows, Alice and Bob are good friends. Today, they agree to play a game together.

At the beginning, each of them has a blank slip of paper. Next, they will write $n$ positive integers in the range $[1,m]$ on their slips, in order. After Alice finishes writing, Bob starts writing his slip after seeing Alice’s slip.

Alice must ensure that the $i$-th number she writes belongs to the set $S_{i}$. Bob must ensure that the $i$-th number he writes belongs to the set $T_{i}$. It is guaranteed that $1 \leq \left|S_{i}\right|,\left|T_{i}\right| \leq 2$.

Alice likes being the same, so she wants the number of positions where her number equals Bob’s number to be as large as possible. Bob likes being different, so he wants the $n$ numbers $b_{1}, \ldots, b_{n}$ he writes to be pairwise distinct. On this basis, Bob wants the number of positions where his number equals Alice’s number to be as small as possible.

Let the numbers written by Alice be $a_{1}, \ldots, a_{n}$, and those written by Bob be $b_{1}, \ldots, b_{n}$. Let $X$ be the number of indices $i$ satisfying $1 \leq i \leq n$ and $a_{i}=b_{i}$. Then:

• Alice wants to maximize $X$.
• Bob, under the condition that $b_{1}, \ldots, b_{n}$ are pairwise distinct, wants to minimize $X$.

You first want to know whether Bob can ensure that the $n$ numbers he writes are pairwise distinct. If Bob can do so, you want to know what the value of $X$ will be when both sides use optimal strategies.

Input Format

This problem has multiple test cases.

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

Then follow $T$ test cases, each in the following format:

The first line contains two positive integers $n,m$, representing the number of integers to be written on the slip and the value range of the integers.

The next $n$ lines describe the sets $S_i$. In each line, the first integer is $\left|S_{i}\right|$, the number of elements in $S_{i}$, followed by $\left|S_{i}\right|$ positive integers describing the elements in $S_{i}$.

The next $n$ lines describe the sets $T_i$. In each line, the first integer is $\left|T_{i}\right|$, the number of elements in $T_{i}$, followed by $\left|T_{i}\right|$ positive integers describing the elements in $T_{i}$.

Output Format

For each test case, output one line: if Bob cannot make the $n$ numbers he writes pairwise distinct, output -1; otherwise, output the value of $X$ when both sides use optimal strategies.

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

1

见附件中的 game/game2.in

见附件中的 game/game2.ans

见附件中的 game/game3.in

见附件中的 game/game3.ans

见附件中的 game/game4.in

见附件中的 game/game4.ans

见附件中的 game/game5.in

见附件中的 game/game5.ans

见附件中的 game/game6.in

见附件中的 game/game6.ans

见附件中的 game/game7.in

见附件中的 game/game7.ans

见附件中的 game/game8.in

见附件中的 game/game8.ans

见附件中的 game/game9.in

见附件中的 game/game9.ans

Hint

[Explanation for Sample 1]

In this sample, $S_{1}=\{3\}$, $S_{2}=T_{1}=\{1,2\}$, $S_{3}=T_{3}=\{3,4\}$, and $T_{2}=\{2,3\}$. Alice has $4$ ways to fill in the numbers, listed as follows:

The first: $a_{1}=3,a_{2}=1,a_{3}=3$.

The second: $a_{1}=3,a_{2}=1,a_{3}=4$.

The third: $a_{1}=3,a_{2}=2,a_{3}=3$.

The fourth: $a_{1}=3,a_{2}=2,a_{3}=4$.

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

The first: $b_{1}=1,b_{2}=2,b_{3}=3$.

The second: $b_{1}=2,b_{3}=3,b_{3}=4$.

The third: $b_{1}=1,b_{2}=2,b_{3}=4$.

The fourth: $b_{1}=1,b_{2}=3,b_{3}=4$.

If Alice chooses the first filling method, then to minimize $X$, Bob chooses the second method, obtaining $X=0$.

If Alice chooses the second filling method, then to minimize $X$, Bob chooses the first method, obtaining $X=0$.

If Alice chooses the third filling method, then to minimize $X$, Bob chooses the first method, obtaining $X=0$.

If Alice chooses the fourth filling method, then no matter which method Bob chooses, $X$ is at least $1$.

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

[Subtasks]

In the table, $\sum n$ and $\sum m$ denote the total sum of $n$ and the total sum of $m$ over all testdata within the same test point. The meanings of $\sum n^{2}$, $\sum m^{2}$, $\sum n^{3}$, and $\sum m^{3}$ are similar. ::cute-table{tuack} | Test Point ID | Constraints | Special Property | |:-:|:-:|:-:| |$1$| $T\le20,n,m\le10$ | | |$2$|^ | ^ | |$3$|^ | ^ | |$4$|^ | ^ | |$5$|^ | ^ | |$6$|$n,m\le200,\sum n^3,\sum m^3\le4\cdot10^7$ | $\text A$ | |$7$| ^ | $\text B$ | |$8$| ^ | $\text C$ | |$9$| ^ | $\text D$ | |$10$| ^ | | |$11$| ^ | ^ | |$12$|$n,m\le2000,\sum n^2,\sum m^2\le4\cdot10^7$ | ^ | |$13$|^ |^ | |$14$|$n,m\le1.5\cdot10^5,\sum n,\sum m\le3\cdot10^5$ |$\text A$ | |$15$| ^ |$\text B$ | |$16$| ^ |^ | |$17$| ^ |$\text C$ | |$18$| ^ |^ | |$19$| ^ | $\text D$ | |$20$| ^ | ^ | |$21$| ^ | | |$22$| ^ | ^ | |$23$|$n,m\le10^6,\sum n,\sum m\le1.5\cdot10^6$ | ^| |$24$| ^ | ^ | |$25$| ^ | ^ |

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_{1} =\{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 in this problem have large input sizes, so we suggest that you use a more efficient input method.

Translated by ChatGPT 5