The Bad Scientist

Sanggeun is a scientist who fabricates his experimental results. He has always tampered with them so carefully that for the past several years nobody has ever caught him. But after going unsuspected for so long, Sanggeun has grown careless with his forgeries.

As a result, his latest paper contains theories that contradict one another. To remove these contradictions, Sanggeun decides to delete some of the theories from the paper. Whenever two theories contradict each other, deleting at least one of the two makes that contradiction disappear.

Meanwhile, Sanggeun's colleague Seonjin has watched all of his experiments over the years. Because of that, there is a limit to how many theories Sanggeun can delete before Seonjin grows suspicious.

The first line contains the number of test cases $T$. ($1 \le T \le 100$)

Each test case is given as follows.

• The first line contains the number of theories $n$ in the paper. ($1 \le n \le 50$)
• The second line contains $k$, the maximum number of theories that can be deleted without arousing suspicion. ($0 \le k \le 16$)
• The third line contains $m$, the number of contradicting pairs of theories. ($0 \le m \le \frac{n(n-1)}{2}$)
• Each of the next $m$ lines contains two theories $x_i$ and $y_i$ that contradict each other. ($1 \le x_i < y_i \le n$)

The theories are numbered from $1$ to $n$, and no pair of theories is given more than once.

For each test case, print on its own line the minimum number of theories that must be deleted so that the paper contains no contradictions.

If that minimum exceeds $k$, so that suspicion cannot be avoided, print IMPOSSIBLE instead.