Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

I. In the News
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

After all other jobs were lost to AI, Ezra decided to become a history teacher. To prepare his class for their future careers (also as history teachers), Ezra wants them to keep up with current events.

There will be $$$n$$$ classes in the semester, and $$$m$$$ news events. The $$$i$$$-th news event will take place between classes $$$l_i$$$ and $$$r_i$$$ inclusive. For each class, a subset of the students has already been chosen to present on news events. During that class, each of the chosen students has to present a news event.

Let's take a look at how students pick events to present. A student is characterized by their enthusiasm $$$e_i$$$. Just before a class when this student is supposed to present, suppose there are $$$x$$$ news events that are currently ongoing and that have not been presented in a previous class. Then, this student will choose $$$\min(x, e_i)$$$ of these events, and be prepared to present any one of their chosen events.

During the $$$i$$$-th class, $$$k_i$$$ students, with enthusiasm levels $$$e_1, e_2, \ldots, e_{k_i}$$$, will be presenting. Ezra can choose the order in which these students present. Each chosen student will choose and present one of the events they prepared that has not been presented by another student. But if a student's prepared topics have all already been presented by others, that student will become embarrassed and drop out of the class. Ezra doesn't want this to happen.

Now, Ezra turns to you for help. Is it possible for him to pick the order in which students present in each class, to guarantee that no student becomes embarrassed, no matter how they choose events?

Input

Input consists of multiple tests. The first line contains $$$t$$$, the number of tests ($$$1 \leq t \leq 10^4$$$).

The first line of each test contains $$$n$$$ and $$$m$$$, the number of classes and the number of events ($$$1 \leq n \leq m \leq 2 \cdot 10^5$$$).

The next $$$n$$$ lines each start with an integer $$$k_i$$$, representing the number of students presenting on day $$$i$$$ ($$$1 \leq k_i \leq m$$$).

This is followed by $$$k_i$$$ integers $$$e_1, e_2, \ldots, e_{k_i}$$$ on the same line  — the enthusiasm levels of the students presenting that day ($$$1 \leq e_i \leq m$$$).

The next $$$m$$$ lines contain two integers $$$l_i$$$ and $$$r_i$$$ each, the predicted start and end dates of the events ($$$1 \leq l_i \leq r_i \leq n$$$).

It is guaranteed that the sum of $$$k_i$$$ in each test does not exceed $$$m$$$. It is also guaranteed that the sum of $$$m$$$ across all tests does not exceed $$$2 \cdot 10^5$$$.

Output

For each test, output YES or NO.

Example
Input
5
3 4
1 3
2 1 1
1 2
1 1
2 2
3 3
2 3
3 4
1 3
2 2 1
1 2
1 1
2 2
3 3
2 3
1 1
1 1
1 1
2 2
1 1
1 1
1 2
1 1
2 2
1 1
1 1
1 2
1 2
Output
NO
YES
YES
NO
YES
Note

In the first test, no matter how Ezra orders the students during class $$$2$$$, he cannot guarantee that no student will get embarrassed. For example, it is possible that both students presenting during class $$$2$$$ pick event $$$4$$$. Since they each only have one topic prepared, the second one to present will get embarrassed. In the second test, this is fixed  — Ezra has the student with $$$e_i = 1$$$ present first. Then, no matter what topic the first student presents, the student with $$$e_i = 2$$$ always has a different topic ready to present.

In the third test, the only student just presents the only topic on the only day.

In the fourth test, it is possible that the student presenting in class $$$2$$$ doesn't have any topic they can prepare! For example, suppose that the student presenting on day $$$1$$$ chooses to present topic $$$1$$$. Then, the student presenting on day $$$2$$$ cannot present topic $$$1$$$ since it was not presented before, and they cannot present topic $$$2$$$ because that event ended after class $$$1$$$. Since they have nothing to present, they become embarrassed.

In the fifth test, note that there may be events that start and end on the same days.