Most Lucky String

Mr. X is planning to visit Ninja Land. Ninja Land has 'N' cities numbered from 0 to 'N-1' and 'M' bidirectional roads. Each road connects two of the 'N' cities, and no two cities have multiple roads between them. All the 'N' cities have a certain 3 letter code given in the array 'ARR'. Mr. X will stay at Ninja land for exactly 'K' days, and he does not like to stay in the same city for two consecutive days. Therefore, he needs to change his city every day of his stay. He also has a special string that is initially empty. Mr. X has a habit that whenever he visits a city, he appends the code of that city to his special string.

Mr. X has a lucky string 'S' of length '3*K'. Mr. X wants to plan his stay in such a manner that the number of places where the final special string differs from the lucky string is the minimum possible. Your task is to find any such order of cities that Mr. X should visit satisfying the above conditions.

Input Format :

The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains three space-separated integers, 'N', 'M' and 'K', denoting the number of cities, the number of bidirectional roads, and the number of cities that Mr. X will visit, respectively. 

The second line of each test case contains 'N' space-separated strings denoting the elements of the array 'ARR'.

The third line of each test contains the special string 'S'.

The next 'M' lines of each test case contain the description of the 'M' roads.
The 'i'th' line contains two space-separated integers, 'City1', 'City2'. 'City1' and 'City2' denote the two cities that are connected by the 'i'th' road.

Output Format :

For each test case, the checker will print "valid" if the returned order of cities results in a string that differs from the lucky string 'S' at the minimum possible places. Otherwise, the checker will print "invalid".
Print the output of each test case in a new line.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
2 <= N <= 1000
1 <= M  <= min(1000,(N*(N-1))/2)
1 <= K <= 100
|ARR[i]| = 3 
|S| = 3*K 
0 <= City1, City2 <= N-1

Every city is reachable from every other city, any two cities are directly connected by at most one road and all the input strings contain uppercase English letters only.

Where 'T' denotes the number of test cases, 'N' denotes the number of cities, 'M' denotes the number of roads, 'K' denotes the number of cities that Mr. X will visit, ARR[i] denotes the 'i'th' element of the array 'ARR', 'S' denotes the lucky string, 'City1' and 'City2' denotes the two cities that are connected by the 'i'th' road, .

Time Limit : 1 sec