11527번 - 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,…,N-1) contains exactly one robot. On each intersection i, there is exactly one red signpost pointing to an intersection, r_i ≠ i, and exactly one green signpost pointing to an intersection g_i ≠ 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.

The first line of input contains a single decimal integer P, (1 ≤ P ≤ 500), 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 which is the number of intersections.
• The second line contains N space separated integers r₀, …, r_N-1 (0 ≤ r_i ≤ N-1 and r_i ≠ i).
• The third line contains N space separated integers g₀, …, g_N-1 (0 ≤ g_i ≤ N-1 and g_i ≠ i).

On some intersections, both signposts might point the same way (i.e. r_i = g_i).

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 case, the button press sequence GREEN, RED, RED, GREEN makes all robots meet at intersection 2.