M. Methodical Mixing
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Agastya and Bathan have been messaging each other very frequently, discussing problem ideas for BAPC and other secret things. Unfortunately, it has come to their attention that Ezra is spying on their communications! As part of an effort to more securely encrypt their messages, Agastya needs to generate a random permutation.

Agastya starts with an integer sequence $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$. Initially, $$$a_i = i$$$ for all $$$1 \le i \le n$$$.

He will perform $$$m$$$ actions on $$$a$$$, described by a length-$$$m$$$ sequence $$$(x_1, y_1), (x_2, y_2), \ldots, (x_m, y_m)$$$ of pairs of integers $$$(1 \le x_i \lt y_i \le n)$$$.

In the $$$p$$$-th action ($$$1 \le p \le m$$$):

  • Agastya swaps the elements $$$a_{x_p}$$$ and $$$a_{y_p}$$$.
  • Then he right-shifts $$$a$$$ by one. More formally, he replaces $$$a_j$$$ with $$$a_{j-1}$$$ for each $$$2 \le j \le n$$$, and replaces $$$a_1$$$ with $$$a_n$$$. For example, right-shifting $$$[1,2,3,4,5]$$$ would give you $$$[5,1,2,3,4]$$$.

Bathan is impressed, of course, but a bit concerned about the security of the permutation. Specifically, he thinks there are $$$q$$$ vulnerabilities. The $$$i$$$-th vulnerability ($$$1 \le i \le q$$$) is described by an integer $$$v_i$$$ and a sequence $$$b_1, b_2, \ldots, b_n$$$ of length $$$n$$$.

If it is possible to do the following operation at most once so that after the $$$v_i$$$-th step, $$$a=b$$$, then Ezra will be able to exploit this vulnerability:

  • Choose some $$$1 \le j \le m$$$. Replace $$$(x_j, y_j)$$$ with any $$$(x_j', y_j')$$$, as long as $$$1 \le x_j' \lt y_j' \le n$$$.

Help the BAPC organizers determine which vulnerabilities Ezra is able to exploit!

Input

Input consists of multiple tests. The first line contains $$$t$$$ ($$$1 \le t \le 10^4$$$).

The first line of each test contains $$$n$$$, $$$m$$$, and $$$q$$$ ($$$2 \le n, m \le 10^5$$$, $$$1 \le q \le 10$$$).

The next $$$m$$$ lines contain $$$2$$$ integers $$$x_i$$$ and $$$y_i$$$, describing the operations ($$$1 \le x_i \lt y_i \le n$$$).

The next $$$q$$$ lines contain $$$n+1$$$ integers each: $$$v_i$$$ and an integer sequence $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le v_i \le m$$$, $$$1 \le b_i \le n$$$).

It is guaranteed that in each vulnerability, $$$b_1, b_2, \ldots, b_n$$$ is a permutation of integers $$$1$$$ through $$$n$$$.

It is also guaranteed that the sum of $$$n$$$ over all tests does not exceed $$$10^5$$$, and the sum of $$$m$$$ over all tests does not exceed $$$10^5$$$. Note that there is no bound on the sum of $$$q$$$ across test cases.

Output

For each query, output YES if Ezra can exploit the vulnerability, and NO otherwise.

Example
Input
2
5 3 5
3 4
1 2
1 5
3 3 4 1 5 2
2 1 2 3 4 5
2 3 2 1 5 4
2 3 5 1 2 4
3 4 3 2 5 1
5 10 10
2 4
1 2
1 5
2 3
1 5
1 5
3 4
2 5
2 4
2 4
8 4 1 5 3 2
3 3 2 1 5 4
9 1 2 3 5 4
6 4 3 2 1 5
10 1 2 5 3 4
5 2 5 4 3 1
10 5 1 2 3 4
4 4 2 3 1 5
5 5 4 2 1 3
2 3 5 1 4 2
Output
YES
NO
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
NO
NO
YES
Note

In the first test:

  • After the first action, $$$a=[5,1,2,4,3]$$$.
  • After the second action, $$$a=[3,1,5,2,4]$$$.
  • After the third action, $$$a=[3,4,1,5,2]$$$.

In the first query, since $$$b_1$$$ is already equal to $$$a$$$ after the third action, we output YES.

In the second query, we can show that it is impossible to change at most one $$$(x_j, y_j)$$$ to make $$$a$$$ equal to $$$b_2$$$ after the second action.

In the third query, we can, for example, change $$$(x_2, y_2)$$$ from $$$(1,2)$$$ into $$$(1,3)$$$. With this change, the second action will first swap $$$a_1$$$ and $$$a_3$$$ to get $$$a = [2,1,5,4,3]$$$, then right-shift to get $$$a=[3,2,1,5,4] = b_3$$$. So we output YES.

In the fourth query, note that if we changed $$$(x_2, y_2)$$$ from $$$(1,2)$$$ into something like $$$(1,1)$$$, then we would get $$$a=[3,5,1,2,4] = b_4$$$ after the second action. But we must maintain $$$x_j \lt y_j$$$, so this is not allowed.

In the fifth query, we can change $$$(x_1, y_1)$$$ from $$$(3,4)$$$ into $$$(1,2)$$$.