Whereas most parks in different parts of the world are inhabited by pleasant little creatures like birds or squirrels, the nature park in Byteland's capital has somewhat larger inhabitants -- a herd of mammoths. As you may well imagine, this does lead to peculiar problems sometimes.

On one occassion the King of Bitland came on a state visit to Byteland, and, to everybody's surprise, decided he would take a stroll in the Mammoth Park. Since mammoths tend to be a little unpredictable and know nothing of the protocol of royal visits, they had to be tied up for the time being. But tying mammoths properly is not as easy as it sounds.

The park consists of little clearings connected by alleys, and on every clearing there stands a mammoth. Due to the lack of sterdy trees in the park, the only things you can tie a mammoth to are other mammoths. Since tying a mammoth by too few ropes may actually be more dangerous than leaving them alone, it is required that each mammoth has to be tied to exactly k other mammoths (that way all animals are kept safe and none of them has a feeling of being unfairly treated). The ropes connecting two mammoths must run along the park alleys and can only be 1 or 2 alleys long (in the latter case, the rope is assumed not to touch the mammoth in between). Finally, no two ropes may run a long a single alley, since this might result in an awful tangle.

It is your task to design which mammoths to tie together, or to determine that the required tethering is impossible to attain.

Input

The first line of input contains integer t, the number of test cases (t<=100). t test cases follow.

The first line of each test case contains three integers n m k, denoting the number of clearings (each with a mammoth on it), the number of alleys in the park, and the number of mammoths to tie each mammoth to, respectively (1<=k<=n<=m<=2000).

Each of the next m lines contains a pair of integers a_i b_i, denoting that clearings a_i and b_i are connected by an alley (1<=a_i,b_i<=n).

Output

For the i-th test case output a line containing the text case i YES if you know a solution to the given problem and case i NO in the opposite case. In the former case, you should then output exactly (k*n)/2 lines, containing the description of a rope between two mammoths. Each such line should begin with integer l, the length of the rope measured in alleys (l=1 or l=2) and be followed by exactly l+1 integers corresponding to successive clearings on the path of the rope.

It is possible that for the given test case no answer exists; in that case the only allowed solutions is case i NO.

Your score is equal to the number of test cases for which you gave the answer case i YES.

Example

Input:
3
4 4 2
1 2
2 3
3 1
1 4
4 4 1
1 2
2 3
3 1
1 4
3 3 2
1 2
2 3
3 1

Output:
case 1 NO
case 2 YES
1 2 3
1 1 4
case 3 NO

Score:
1+0+0 = 1

For the presented example, the optimal solution would score 2 points (for test cases 2 and 3).