Exploration Team

Air pollution and the carbon dioxide in the atmosphere are warming the planet. Ice at the North Pole is melting and the sea level is rising, so many cities will end up under water. Abnormal weather is appearing all over the world. To survey the exact state of the North Pole, the International Climate Protection Committee (ICPC) decided to put together an exploration team.

The committee collected a list of applicants and recorded every friendship among them. To pick a team that cooperates closely, the committee set the following rule.

Eligibility: every member of the team must have at least $k$ of their own friends in the team.

Among the eligible teams the committee picks one of maximum size. For example, suppose there are 5 applicants and the friendships are $(1, 2)$, $(2, 3)$, $(3, 4)$, $(4, 5)$, $(2, 5)$, $(2, 4)$. If $k = 2$, each of $\{2, 3, 4\}$, $\{2, 4, 5\}$, $\{2, 3, 4, 5\}$ satisfies the rule, and the largest of them has size 4, so the committee picks $\{2, 3, 4, 5\}$. If $k = 3$, no team satisfies the rule.

Given the friendships among $n$ applicants and an integer $k$, write a program that finds the maximum size of an exploration team satisfying the rule.

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

The first line of each test case contains three integers $n$, $k$, $f$ separated by single spaces. ($1 \le k < n \le 2000$, $1 \le f \le n(n-1)/2$) Here $n$ is the number of applicants, $k$ is the number used in the eligibility rule, and $f$ is the number of friendships. The applicants are numbered from $1$ to $n$.

Each of the next $f$ lines contains the numbers of two applicants who are friends, separated by a single space.

For each test case, print the maximum size of the exploration team on its own line. If no team satisfies the rule, print $0$.