Robots

While you were not watching, your $N$ robots started moving on their own and spread across your hometown. The town has $N$ intersections numbered 0 through $N-1$, and exactly one robot stands on each intersection. Intersection $i$ carries one red signpost that points at an intersection $r_i \neq i$ and one green signpost that points at an intersection $g_i \neq i$.

When you press the red button on the remote control, every robot moves along the red signpost at the same time: a robot on intersection $i$ moves to $r_i$. When you press the green button, every robot moves to $g_i$ instead. Write a program that decides whether some sequence of button presses brings all $N$ robots to the same intersection at the same time.

The first line contains the number of data sets $P$ ($1 \le P \le 500$). The data sets are independent and are processed the same way.

Each data set consists of three lines.

• The first line contains the data set number $K$ and the number of intersections $N$. The data sets are numbered 1 through $P$ in order.
• The second line contains $r_0, \ldots, r_{N-1}$ separated by spaces ($0 \le r_i \le N-1$, $r_i \neq i$).
• The third line contains $g_0, \ldots, g_{N-1}$ separated by spaces ($0 \le g_i \le N-1$, $g_i \neq i$).

$2 \le N \le 500$, and the sum of $N$ over all data sets is at most 2000. Both signposts on an intersection may point the same way, so $r_i = g_i$ is possible.

Print one line per data set. The line contains the data set number $K$, one space, then YES if you can gather every robot on one intersection, or NO otherwise.

In the second data set of the example, pressing GREEN, RED, RED, GREEN gathers every robot on intersection 2.