The population of Mars has increased rapidly and so has the traffic on its highways. This not only increased traffic jams but also made it difficult to locate outlaws in rush hours. So, the traffic authority has decided to establish a monitoring system on the highway. The idea is like this they will setup some traffic cameras at some strategic points. These cameras will constantly monitor the traffic passing by (in both directions) and record the video footage for future analysis. The scientists working at Mars are pretty smart. They have a large number of cities and they designed the highways as segments between these cities (and nothing else). What this means is that each highway segment starts and finishes at exactly two different city junctions. No two highways meet anywhere other than at a city junction. Also note that all highway segments allow two-way traffic. In order to avoid theft of cameras, the traffic authority wants to setup cameras only at these city junctions. The cameras can take pictures from all directions simultaneously. So a camera at a city junction can monitor all the highway segments ending at that junction. Imagine yourself as a scientist in Mars. You are given a certain number of cameras and a description of all highway segments you need to monitor. You are to determine whether it is possible to monitor all the highway segments using the given number of cameras. Moreover, if it is possible indeed, you are to identify the city junctions where you may place the cameras. Input The input file will contain multiple test cases. First line of input contains a single integer that specifies how many test cases you have in the input (2 in sample input). Actual test data starts from the next line. First line of test data contains three integers: N, 1 ≤ N ≤ 1000, H and K, 1 ≤ K ≤ 18. Here N is the number of city junctions, H is the number of highway segments among them and K is the number
2/2 ofcameras. InthefirsttestcaseofsampleinputwehaveN=5,H=7andK=2. NextHlines describe the highway segments, one segment in each line. Each highway segment is described by two integers x and y which specify that we have a (two-way) highway segment between city junctions x and y. Next test case begins at the end of this highway segment list. You can assume that there is at most 15 test cases. A cautionary note: The number of city junctions can be as high as 1000. Output For each test case, first you have to print the test case number as shown in the sample output. Then you have to print ‘yes’ or ‘no’ depending on whether you can monitor all the described highway segments with at most the given number of cameras. Moreover, if your answer is ‘yes’, you have to print a list of city junctions (in any order) where you will setup the cameras. Note that there can be multiple such lists. In this case you may print any such list that satisfies the requirement. The entire output corresponding to a test case must be in a single line. Sample Input 2 572 12 13 15 24 25 35 45 573 12 13 15 24 25 35 45 Sample Output Case #1: no Case #2: yes 1 2 5