Problem H

Millennium Ceremony

Input: Standard Input

Output: Standard Output

Time Limit: 2 Seconds

On an ancient island, people are holding a Millennium Ceremony in a beautiful palace. The palace has n normal layers; each is in the shape of a perfect circle. Layers are numbered 1, 2, 3 ... n from bottom to top. There are exactly m(m is even) stelae on each circle, which divide the circle into m identical parts. One each layer, the stelae are numbered 1, 2, 3 ... m in counter-clockwise order. Each stele has exactly two neighbors.

The Grand Altar is at the center of the bottom (you may call it layer 0, it is below layer 1), which is the starting point of the whole ceremony. The Holy Torch is hanging at the ceiling of the palace(you may call it layer n+1, it is above layer n). In these two special layers(layer 0 and layer n+1), there are no stelae.

On any middle layer i (i.e 1 < i < n), each stele is tied with 2k+2 ropes. Two of them are tied on the two neighboring stelae on the same layer(one rope each each neighbor), we call those 2 ropes 'intra-layer ropes'. Besides, k of them are tied with k different stelae on layer i-1, while k of them are tied with k stelae on layer i+1. These 2k ropes are called 'inter-layer ropes'. Intra-layer ropes and inter-layer ropes are shown in picture (a). To make the palace look more beautiful, the number of two ending stelae of an inter-layer rope must have the same parity (i.e both odd or both even) and k is always odd.

Every stele on layer 1 is connected to The Grand Altar with a rope, these ropes are called 'Altar-ropes', while every stele on layer n is connected to The Holy Torch with a rope, these ropes are called 'Torch ropes'. These ropes are shown in picture (b) and (c).

You may have calculated that there are (n-1)*m*k inter-layer ropes, n*m intra-layer ropes, m Altar-ropes and m Torch ropes. Altogether, there are m*(n*k-k+n+2) ropes in total.

At the beginning of the ceremony, two heroes Chris and Chirt must light up The Holy Torch. According to the custom there, they should move from The Grand Altar to The Holy Torch, then back to The Grand Altar. They can move along a rope from one place(Altar, Torch or a stele) to another, but each rope should be passed by exactly twice: one for each person. Chiris goes first, after he comes back, Chrit goes.

The ropes are magic. They are transparent before Chris starts his trip, but if someone is reaching a stele or The Holy Torch for his first time, the rope he has just passed by changes its color! The color it's changing to depends on the person and the type of the rope, shown below.

Person	intra-layer ropes	other ropes
Chris	Golden	Dark Grey
Chrit	Silver	Light Grey

Note that Chrit should never make a color-changed rope change its color again, so if he is facing a stele or The Holy Torch which he has never been to, he can go there if and only if the rope he will pass by is still crystal-transparent.

If you understand all the things above, you will know that after Chrit's trip, golden ropes and dark-grey ropes should be n*m+1 in total, while the silver ropes and light-grey ropes are also n*m+1, because for each of the n*m stelae, and for The Holy Torch, there is exactly one color-changed rope changed color when someone reached the stelae or The Holy Torch for his first time.

Now, Here comes the ultimate mission for Chris and Chrit! When they finished their trip, each layer should be decorated by alternated golden-silver ropes! (i.e golden->silver->golden->silver->golden->silver...) No intra-layer ropes may remain transparent, and no two neighboring intra-layer ropes should be in the same color! If this is done, imagine how splendid the palace looks!

Help Chris and Chrit to make the palace surrounded by golden-silver rings!

Input

The first line contains the number of tests t(1<=t<=15). Each case contains several lines. The first line contains three integers n, m, k(1<=n, m<=50, 1<=k<=9, m is even, k is odd). There are n-1 blocks follow. The i-th block(1<=i<=n-1) describes the inter-layer ropes between layer i and layer i+1. The block contains m lines, the j-th line(1<=j<=m) contains k integers, indicating the numbers of k stelae on layer i+1 that are connected with j-th stele on layer i.

Output

For each test case, the first line should be the case number and your yes-no answer. If there is an answer, print 'Yes', otherwise print 'No'. If the answer is 'Yes', print 2*m*(n*k-k+n+2) lines. The first m*(n*k-k+n+2) lines describe Chiris' route. The i-th line among them contains two integers (x, y), indicating Chiris is at the y-th stele on layer x after he passed the i-th rope on his trip. x = 0 means The Grand Altar, while x = n+1 means The Holy Torch. The second m*(n*k-k+n+2) lines describe Chrit's route, the format is the same. If there are more than one solution, any one is ok.

Sample Input Output for Sample Input

2 4 1

1 6 1

Case 1: Yes

1 2 1 3 0 0 1 4 1 1 1 2 2 2 2 3

1 3 1 4 2 4 2 1 2 2 3 0 2 3 2 4

3 0 2 1 1 1 0 0 1 3 1 4 0 0 1 1

1 2 1 3 2 3 2 4 1 4 1 1 2 1 3 0

2 4 2 1 2 2 2 3 3 0 2 2 1 2 0 0

Case 2: Yes

1 4 1 5 0 0 1 2 1 3 0 0 1 6 1 1

1 2 2 0 1 5 1 6 2 0 1 3 1 4 2 0

1 1 0 0 1 5 1 6 0 0 1 3 1 4 0 0

1 1 2 0 1 4 1 5 2 0 1 6 1 1 1 2

1 3 2 0 1 2 0 0

Special note: The sample output is too long. We combine 8 lines into one in the table above to reduce the length of the table, but keep in mind that the real output should contain only two integers each line.

Problemsetter: Rujia Liu, Member of Elite Problemsetters' Panel

Problem Source: IOI2003 China Team Selective Contest