Due to the disorganized structure of his mootels (much like motels but with bovine rather than human guests), Farmer John has decided to take up the role of the mootel custodian to restore order to the stalls.

Each mootel has N stalls labeled 1 through N (1≤N≤10⁵) and M (0≤M≤10⁵) corridors that connect pairs of stalls to each other bidirectionally. The ith stall is painted with color Ci and initially has a single key of color Si in it. FJ will have to rearrange the keys to appease the cows and restore order to the stalls.

FJ starts out in stall 1 without holding any keys and is allowed to repeatedly do one of the following moves:

- Pick up a key in the stall he is currently in. FJ can hold multiple keys at a time.

- Place down a key he is holding into the stall he is currently in. A stall may hold multiple keys at a time.

- Enter stall 1 by moving through a corridor.

- Enter a stall other than stall 1 by moving through a corridor. He can only do this if he currently holds a key that is the same color as the stall he is entering.

Unfortunately, it seems that the keys are not in their intended locations. To restore order to FJ's mootel, the ith stall requires that a single key of color F_I is in it. It is guaranteed that S is a permutation of F.

For T different mootels (1≤T≤100), FJ starts in stall 1 and needs to place every key in its appropriate location, ending back in stall 1. For each of the T mootels, please answer if it is possible to do this.

#5637 upload 4 done - how_to_reg -

Custodial Cleanup timer 1s memory 64MB

#5637

Custodial Cleanup 1s 64MB