I :: Moein is a Cheater

Time Limit: 5 Seconds    Memory Limit: 32768 KB
Special Judge

Moein has done all the cheating he could to eventually reach the ACM-ICPC World Finals. In addition to his team, N other teams, represented with 1, 2, 3, ..., N, have participated in the contest and some of those teams are friends with each other. On the opening day, he intends to have a chat with the other teams and share the ideas of the newest methods of cheating. He starts the first conversation with an arbitrary team. However, starting to chat with a team about cheating is somewhat difficult; therefore, after finishing his chat with team T, he asks them to introduce him to the next team. Team T accepts to do so only if they are friends with team S via at most K intermediaries. (e.g. If T and S are friends, they’re friends via zero intermediaries, but if they’re not friends with each other and have a mutual friend, they are friends via one intermediary.)

Moein is seeking the longest sequence of chats such that he chats with each team at most once. Help him find this sequence.

Input

The first line contains the number of test cases T.

For each test, the first line contains three integers N (3 ≤ N ≤ 1000), K(2 ≤ K ≤ N) and M (1 ≤ M ≤ 10⁵) the number of friendships between teams.

After that there are M lines each containing 2 integers x and y, that show x and y are friends (1 ≤ x < y ≤ N).

Output

In the first line of output print the length of longest sequence, and print the sequence in the next line. 

If there are more than one sequence with the longest length, print one of them arbitrarily.

Sample Input

1
4 2 3
1 2
1 3
1 4

Sample Output

4
1 2 3 4

Submit

Source: 15th Iran Nationwide Internet Contest