OpenKattis Kattis Set 06 - CS2040/C/S++ Basic Graph Review

Start

2021-02-15 04:00 AKST

Kattis Set 06 - CS2040/C/S++ Basic Graph Review

End

2021-03-01 00:30 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -339 days 18:19:55

332:30:00

0:00:00

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