Submit | All submissions | Best solutions | Back to list |

## WPCC - C Connect the dots (professional) |

At school, Jack painted a picture consisting of n dots numbered from 1 to n and connected using n-1 line segments, such that it was possible to get from every dot to every other dot, possibly visiting other dots on the way. Next, Jack made n copies of the picture on a Xerox machine and burned the original. Unfortunately, a goblin living in the machine removed a piece from every copy of the picture: from the i-th copy, he removed the dot numbered i along with all adjacent line segments. Then, the goblin erased all the dots' numbers and relabelled the dots, using numbers 1, ..., n to enumerate the remaining n-1 dots.

Jack repeated the whole process and drew several more pictures. The goblin was delighted and also repeated his wrongdoing for every picture. This way, Jack ended up with plenty of copies.

On his way home, Jack was ambushed by three thugs, who took some of the copies. They left him only the k ugliest ones. Jack came home in tears. He now wants to recover at least one picture. Jack called you on the phone and described the layout of the line segments on his k remaining copies. The copies might also contain dots which aren't connected to anything, but Jack never thought to mention them to you.

**Multiple test cases**

The first line of the input contains Z ≤ 20 - the number of test cases. Z descriptions of single test cases follow.

**Single test case**

The first line of input contains the numbers n and k. In the following lines, the descriptions of the k copies are given. The description of the i-th copy is a line containing m_{i} - the number of line segments on this copy, followed by m_{i} lines, each of them containing two space-separated integers: the numbers of two dots connected by a line segment.

**Bounds**

Basic: 2 ≤ n ≤ 100, k = n.

Professional: 2 ≤ n ≤ 1000, k = 2.

**Output**

If Jack's copies can't possibly come from a single picture, you should output the word NO. Otherwise, output one line containing the word YES and n-1 lines describing any picture that Jack's copies could have come from. For every line segment you should output the numbers of dots connected with it, separated with a single space. If there are many solutions, print any of them.

**Sample input for the basic version**

1 5 5 2 4 1 2 1 1 3 1 3 4 1 4 3 2 1 3 3 1 3 2 4 1 3 2 1 3 2 4 2

**Sample output for the basic version**

TAK 2 1 3 2 4 2 1 5

**Sample input for the professional version**

1 9 2 6 4 3 5 4 6 1 8 6 8 2 7 1 5 8 6 8 7 8 1 7 3 5 1

**Sample output for the professional version**

TAK 2 1 3 1 5 4 6 5 7 6 8 5 9 8 1 4

Added by: | gawry |

Date: | 2011-10-07 |

Time limit: | 0.134s-4.070s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM64 |