Hide

Problem I
Robots

While you weren’t watching, your $N$ robots have developed a life of their own and spread throughout your hometown. Each of your hometown’s $N$ intersections (numbered $0, \ldots , N-1$) contains exactly one robot. On each intersection $i$, there is exactly one red signpost pointing to an intersection, $r_ i \ne i$, and exactly one green signpost pointing to an intersection $g_ i \ne i$. When you press the red button on your remote control, each robot will move to the intersection indicated by the red signpost (robots at intersection $i$ move to $r_ i$). When you press the green button, each robot will move to the intersection indicated by the green signpost (robots at intersection $i$ move to $g_ i$). Write a program that determines whether you can make the robots all meet at the same intersection at the same time via some sequence of commands on your remote control.

Input

The first line of input contains a single decimal integer $P$, ($1 \le P \le 50$), which is the number of data sets that follow. Each data set should be processed identically and independently.

Each data set consists three lines of input as follows:

  • The first line contains the data set number, $K$, followed by a single integer $N$ ($1 \le N \le 500$) which is the number of intersections.

  • The second line contains $N$ space separated integers $r_0, \ldots , r_{N-1}$ ($0 \le r_ i \le N-1$ and $r_ i \ne i$).

  • The third line contains $N$ space separated integers $g_0, \ldots , g_{N-1}$ ($0 \le g_ i \le N-1$ and $g_ i \ne i$).

On some intersections, both signposts might point the same way (i.e. $r_ i = g_ i$).

Output

For each data set there is one line of output. The single output line consists of the string ’YES’ if you can make all robots meet or ’NO’ otherwise.

Note

For the second sample input case, the button press sequence GREEN, RED, RED, GREEN makes all robots meet at intersection $2$.

Sample Input 1 Sample Output 1
2
1 4
1 2 3 0
3 0 1 0
2 4
1 2 3 0
2 2 1 2
1 NO
2 YES

Please log in to submit a solution to this problem

Log in