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?

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.

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$.

Sample Input 1 | Sample Output 1 |
---|---|

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 |