Elf Tournament Bracket

The elf country is holding an elimination tournament, and $2^N$ elves want to take part. When the tournament starts, each elf receives a distinct ID number from 1 to $2^N$, and the elf president lines them all up in an order of their own choosing.

A match is played by two elves, and every match produces one winner and one loser. There are no draws. In round 1 the first elf in the line plays the second elf, the third elf plays the fourth elf, and so on. After round 1 the $2^{N-1}$ elves that lost leave the line, and the $2^{N-1}$ elves that won stay in their original relative order. The remaining elves then play round 2 the same way. After $N$ rounds one elf is left, and that elf wins the tournament.

$M$ of the elves are sensitive, which means they become very sad when they have to play against a friend. Precisely, the sensitive elf $E_i$ becomes sad if it plays against one of its friends in any of rounds 1 through $K_i$. Friendship can go one way only. One elf may treat another elf as a friend while the other one does not.

Decide whether the president can fix a starting order that leaves no elf sad, whatever the results of the matches turn out to be.

The first line has the number of test cases $T$. The first line of each test case has two integers $N$ and $M$. The $M$ sensitive elves follow, two lines each. The first line has three integers $E_i$, $K_i$, $B_i$, and the second line has the $B_i$ ID numbers of the elves that elf treats as friends.

Limits

• $1 \le T \le 200$
• $1 \le N \le 3$
• $0 \le M \le 2^N$
• $1 \le E_i \le 2^N$, and the $M$ values $E_i$ are all different.
• $1 \le K_i \le N$
• $1 \le B_i$, and the $B_i$ ID numbers on one line are different from each other and from $E_i$.
• $M \le B_1 + B_2 + \cdots + B_M \le \min(2M, 2^N)$

For each test case, print Case #x: on one line, then YES if a starting order that satisfies the condition exists and NO otherwise. Here $x$ is the test case number, starting from 1.