Treasure Chests (Small)

You followed an old map and found the secret treasure trove of Larry the pirate.

The trove holds $N$ locked chests. Each chest opens with one key of a specific type, and a key that opens a chest is gone and cannot be used again. Every chest holds treasure, and it may also hold keys that open other chests. A chest may hold several keys of the same type, and you may carry any number of keys.

You start with at least one key, and the map records which keys sit inside which chest. Use that information to find an order that opens every chest.

For example, suppose there are four chests as listed below and you start with a single key of type 1.

Opening them in the order 2, 1, 4, 3 opens all four chests. If you open chest 1 first, you spend your only key and no chest can be opened after that.

The first line contains the number of test cases $T$. The $T$ test cases follow.

The first line of each test case contains two positive integers $K$ and $N$, the number of keys you start with and the number of chests you must open.

The next line contains $K$ integers, the types of the keys you start with.

Each of the next $N$ lines describes one chest. Line $i$ begins with two integers $T_i$ and $K_i$, the key type needed to open chest $i$ and the number of keys inside that chest. Then come $K_i$ integers, the types of the keys inside that chest.

Limits

• $1 \le T \le 25$
• $1 \le K$
• Every key type is an integer between $1$ and $200$.
• $1 \le N \le 20$
• In each test case, the keys you start with and the keys inside the chests add up to at most 400 keys.

For each test case, print one line in the form Case #x: C1 C2 ... CN, where $x$ is the test case number starting from 1 and $C_i$ is the number of the $i$th chest you open. Chest numbers start from 1.

If several orders open all the chests, print the lexicographically smallest one. That is, make $C_1$ as small as possible, and among the orders that do so make $C_2$ as small as possible, and continue the same way for the later positions.

If no order opens all the chests, print Case #x: IMPOSSIBLE for that test case.