Two parties

You want to throw a party with all your friends, but unfortunately some of them hate each other. So you decide to make two parties instead of one, inviting each friend to exactly one party, and avoiding two people who hate each other going to the same party. Can you do it?

Input

Input consists of several cases, each with the number of friends $a$ , followed by their $a$ names, all different and in any order. Follow the number of hate relationships $m$ , and the $m$ pairs of friends $x$ and $y$ that hate each other.

Suppose $2 \le a \le 10^4$ , that the names are words with between one and six lowercase letters, $1 \le m \le 5a$ , $x \ne y$ , that both $x$ and $y$ appear in $a$ ’s friends list, and that no hate relationship appears more than once.

Output

Print one line for each case. If there is no solution, print “NO”. Otherwise, print “SI” followed by the names of the participants in either party, in any order. If there is more than one solution, choose anyone. Follow the format of the examples exactly.

Problem information

Author: Unknown
Translator: Salvador Roura
Event: Examen extraordinari d’Algorísmia, FME
Date: 2017-06-27

Generation: 2026-07-02T12:03:02.733Z