Hide

# Problem IRobots

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