Millennium Ceremony

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 Chris Chrit intra-layer ropes Golden Silver other ropes Dark Grey Light Grey

2/3 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 linecontainsthreeintegersn,m,k(1≤n,m≤50,1≤k≤9,miseven,kisodd). Therearen−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’,otherwiseprint‘No’. Iftheansweris‘Yes’,print2∗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 meansTheGrandAltar,whilex=n+1meansTheHolyTorch. Thesecondm∗(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. Special note: The sample output is too long. We combine 8 lines into one in the table below to reduce the length of the table, but keep in mind that the real output should contain only two integers each line. Sample Input 2 241 1 2 3 4 161 Sample Output Case 1: Yes 1213001411122223 1314242122302324 3021110013140011

3/3 1213232414112130 2421222330221200 Case 2: Yes 1415001213001611 1220151620131420 1100151600131400 1120141520161112 13201200