There is a sequence $$$A$$$ of length $$$m$$$ where all elements equal to $$$0$$$. We will then execute $$$n$$$ operations on $$$A$$$ in order. The $$$i$$$-th operation can be denoted as $$$p_i$$$ distinct integers $$$b_{i, 1}, b_{i, 2}, \cdots, b_{i, p_i}$$$, indicating that we'll change the value of the $$$b_{i, j}$$$-th element in the sequence to $$$i$$$ for all $$$1 \le j \le p_i$$$. Let $$$R$$$ be the resulting sequence after all operations.
We now require you to rearrange the operations but still produce the same result. More formally, let $$$q_1, q_2, \cdots, q_n$$$ be a permutation of $$$n$$$ that differs from $$$1, 2, \cdots, n$$$. You'll execute the $$$q_1$$$-th, $$$q_2$$$-th, ..., $$$q_n$$$-th operation on sequence $$$A$$$ in order, and the final resulting sequence must equal to $$$R$$$. Your task is to find such permutation or state that it does not exist.
Recall that a permutation of $$$n$$$ is a sequence of length $$$n$$$ in which each integer from $$$1$$$ to $$$n$$$ (both inclusive) appears exactly once. Let $$$x_1, x_2, \cdots, x_n$$$ and $$$y_1, y_2, \cdots, y_n$$$ be two permutations of $$$n$$$. We say they're different if there exists an integer $$$k$$$ such that $$$1 \le k \le n$$$ and $$$x_k \ne y_k$$$.
There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^5$$$) indicating the number of operations and the length of the sequence.
For the following $$$n$$$ lines, the $$$i$$$-th line first contains an integer $$$p_i$$$ ($$$1 \le p_i \le m$$$) indicating the number of elements changed by the $$$i$$$-th operation. Then $$$p_i$$$ distinct integers $$$b_{i,1}, b_{i,2}, \cdots, b_{i,p_i}$$$ follow ($$$1 \le b_{i,j} \le m$$$) indicating the index of the elements to be changed.
It is guaranteed that the sum of $$$(n + m)$$$ of all test cases will not exceed $$$2 \times 10^6$$$, and the sum of $$$p_i$$$ of all test cases will not exceed $$$10^6$$$.
For each test case, if such permutation exists, first output Yes in one line. Then output $$$n$$$ integers $$$q_1, q_2, \cdots, q_n$$$ separated by a space in the second line indicating the answer. If there are multiple valid answers, you can output any of them.
If there is no such permutation, simply output No in one line.
Please, DO NOT output extra spaces at the end of each line, or your solution may be considered incorrect!
33 63 3 1 52 5 32 2 62 33 1 3 22 3 11 32 2 1
Yes 3 1 2 No No
For the first sample test case, by executing the operations in either order of $$$\{1, 2, 3\}$$$ or $$$\{3, 1, 2\}$$$ yields the same resulting sequence $$$\{1, 3, 2, 0, 2, 3\}$$$.
Name |
---|