Problem G
Paintings

Image by William Fiset, CC BY-SA 4.0

Catherine recently got into painting minimalist art. For her next painting she wants to create an image with $N$ vertical strips of distinct colors. She always begins painting her vertical strips on the left side of the canvas and proceeds to the right side. However, there are certain pairs of colors Catherine does not like seeing next to each other. If two such colors are adjacent in a painting, she considers this painting to be hideous. Furthermore, there are colors Catherine prefers over other colors, so when painting she always selects her most preferred unused color that does not make the painting (as created so far) hideous, and that allows her to complete a non-hideous painting. Can you help Catherine find her favorite painting?

Input

The first line of input contains an integer $T$ $(1 \leq T \leq 5)$ denoting the number of test cases that follow.

The first line of each test case contains one integer $N$ $(3 \leq N \leq 12)$, where $N$ is the number of colors/vertical strips Catherine wants her painting to have. On the second line are $N$ colors ordered in (strictly) decreasing order of preference, where each color is a string of between $1$ and $20$ lowercase letters (a–z). The third line contains a positive integer $M$ indicating the number of pairs of colors that follow. Each of the next $M$ lines contains two space-separated colors $c_ i$ and $c_ j$ $(c_ i \neq c_ j)$ such that Catherine does not like seeing color $c_ i$ next to color $c_ j$. No pair of colors will appear on more than one line.

Output

For every test case output two lines. On the first line display the total number of paintings Catherine can make that are not hideous (without consideration for her color preferences), and on the second line output Catherine’s favorite painting as a space-separated list of colors corresponding to the strips in the painting from left to right.

Note: You are guaranteed that there is always at least one arrangement of colors Catherine finds non-hideous, and that the maximum number of paintings Catherine can make is less than $100\, 000$.

3
3
green red blue
1
red blue
4
purple pink red black
2
purple pink
red black
8
black white red blue yellow green orange purple
6
black white
blue green
orange black
red blue
green yellow
white purple

2
red green blue
8
purple red pink black
7208
black red white blue yellow orange green purple