Description

Given $n$ queues, each containing $m$ positive integers, all of which are less than or equal to $n$, the $i$-th queue's $j$-th element is $a_{i,j}$, where $a_{i,1}$ is the head of the queue and $a_{i,m}$ is the tail of the queue.

Now, you hold the number $0$. You need to select one queue, place $0$ at its tail, and take the head of the queue into your hand.

Next, you will repeat the operation until you take $0$ back into your hand:

• Let the number in your hand be $p$. Place it at the tail of the $p$-th queue and take the head of the $p$-th queue into your hand.

Now, Little Y wants to know if, over an infinite amount of time, you can avoid taking back $0$. If you can, output Yes, otherwise, output No.

Input Format

There are multiple test cases for this problem.

The first line contains an integer $T$, representing the number of test cases.

For each test case:

• The first line contains two integers $n$ and $m$.
• The next $n$ lines, each containing $m$ integers, represent the $i$-th queue's elements $a_{i,j}$.

Output Format

For each test case, output one line containing Yes if you can avoid taking back $0$, otherwise output No.

1
3 2
2 2
3 3
1 1

No

1
3 2
2 1
3 3
2 2

Yes

Hint

Explanation

Sample 1:

Below is a simulation where $0$ is initially placed into the first queue.

// Number in hand:
0
// Queue contents (leftmost is the head, rightmost is the tail):
2 2
3 3
1 1

// Number in hand:
2
// Queue contents:
2 0
3 3
1 1

// Number in hand:
3
// Queue contents:
2 0
3 2
1 1

// Number in hand:
1
// Queue contents:
2 0
3 2
1 3

// Number in hand:
2
// Queue contents:
0 1
3 2
1 3

// Number in hand:
3
// Queue contents:
0 1
2 2
1 3

// Number in hand:
1
// Queue contents:
0 1
2 2
3 3

// Number in hand:
0
// Queue contents:
1 1
2 2
3 3

Sample 2:

By simulation, we can see that only when $0$ is initially placed into the first queue can it never be picked up again.
This is because after several rounds, the second queue will be filled with the number $2$, and the number in hand will also be $2$, so the process will loop indefinitely within the second queue.

Constraints

This problem uses subtask scoring.

• Subtask 1 (20 points): $n \leq 2$.
• Subtask 2 (10 points): $\forall a_{i,j} = i$.
• Subtask 3 (20 points): $n \times m \leq 1000$.
• Subtask 4 (50 points): No special restrictions.

For all data:

• $1 \leq T \leq 10$.
• $1 \leq n \times m \leq 10^5$.
• $1 \leq a_{i,j} \leq n$.