N. Networks Make the Net Work
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice, Bob, and Cindy are learning networking in the computer club! Each of them started with five computers; each computer has a unique name to identify it. Cables can be used to directly connect two different computers; each cable is two-way. A collection of computers and cables is called a network. Their networks are originally configured in the following shapes (for privacy reasons, we've hidden the computers' names).

Occasionally, they may need to add a repeater computer in order to extend a connection.
Formally, in order to extend the connection between computers $$$u$$$ and $$$v$$$ (where $$$u$$$ and $$$v$$$ are distinct computers already connected by a cable), one would do the following:
  • Acquire a new computer (say its name is $$$x$$$)
  • Discard the cable connecting $$$u$$$ and $$$v$$$, then add two new cables connecting $$$u$$$ and $$$x$$$, and $$$x$$$ and $$$v$$$.
Each of them then performed this "insert a repeater" connection some unknown number of times to their network.

They decide to give you a little puzzle. They'll give you the setup of a computer network. Whose is it! The answer could be even "none of them", and you also need to be able to identify if this is the case. Also, please answer $$$T$$$ different test cases per file.

Input

The first line of input contains a single integer $$$T$$$. Then, the descriptions of each of the $$$T$$$ test cases follows.

The first line of each test case contains two space-separated integers $$$n$$$ and $$$m$$$.

The second line of each test case contains $$$n$$$ space-separated strings, the names of the computers in the presented network.

Then, $$$m$$$ lines follow, each containing two space-separated strings. These strings are names of computers, and it means, "There exists a cable that connects these two computers"

Output

For each test cases, output the answer to that test case:

Consider the set of all people (among Alice and Bob and Cindy) such that it is possible for this person to have been the owner of the presented network, i.e. the set of all names that can fill in the blank in: "It is possible that the owner of this network is _____". Output a line containing their space-separated names, sorted in lexicographic (dictionary) order.

If none of them could possibly be the owner of the presented network, output PRANKED instead.

Scoring

Here, $$$N$$$ denotes the sum of $$$n$$$s in a single test file, and $$$M$$$ the sum of $$$m$$$s in a single test file.

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 0 \leq T \\ 1 \leq n \leq 2 \times 10^5 \\ N \leq 2 \times 10^5 \\ 0 \leq m \leq 2 \times 10^5 \\ M \leq 2 \times 10^5 \\ \text{Each computer's name is distinct, and consists} \\ \text{of at most $5$ upper and lowercase letters.} \\ \text{No cable connects a computer to itself.} \\ \text{At most one cable connects any pair of computers.} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{20} & \text{Someone owns each network.} \\ \hline 2 & \mathbf{20} & \text{Neither Alice nor Bob own each network.} \\ \hline 3 & \mathbf{20} & \text{Neither Alice nor Cindy own each network.} \\ \hline 4 & \mathbf{20} & \text{Neither Bob nor Cindy own each network.} \\ \hline 5 & \mathbf{20} & \text{No further constraints} \\ \hline \end{array}\\

\end{align*}$$$$$$

Example
Input
3
6 6
CompA CompB CompC CompD CompE CompF
CompA CompB
CompA CompC
CompC CompD
CompB CompD
CompB CompE
CompD CompF
7 7
CompA CompB CompC CompD CompE CompF CompG
CompA CompB
CompB CompC
CompC CompD
CompD CompE
CompE CompA
CompD CompF
CompD CompG
8 7
CompA CompB CompC CompD CompE CompF CompG CompH
CompA CompH
CompB CompH
CompB CompG
CompC CompG
CompC CompF
CompD CompF
CompD CompE
Output
Alice
PRANKED
Cindy
Note

Here are computer networks in the sample test cases: