Time Limit: 2 second(s) | Memory Limit: 32 MB |
'Wishing Snake' is a computer game for children. In this game, there is a big board and a snake. The board contains 1000 check points numbered from 0 to 999. And the snake can go from any checkpoint to another without crossing other checkpoints. Initially the snake is at checkpoint 0.
Now n children come in front of the board and they start to wish. Each wish is like "I want to see the snake walking from checkpoint u to checkpoint v." And the snake can fulfill this wish by walking from checkpoint u to checkpoint v without crossing any other checkpoints. Each child can have multiple wishes. At first a child comes in front of the board and makes his wishes. After that a new child comes and makes his new wishes (that means not wished by any children yet). And it continues until the nth children.
After that the snake starts walking from one checkpoint to another. It can only walk from one checkpoint to another if any child had wished it. The snake wants to fulfill all the wishes done by all the children in one single path. Since you are the main designer of the game; you want to find whether it's possible or not.
Input starts with an integer T (≤ 65), denoting the number of test cases.
Each case starts with an integer n (1 ≤ n ≤ 100). Then for each child an integer k (k ≥ 0) is given. Each of the next k lines contains two integers u v (0 ≤ u, v < 1000, u ≠ v) denoting that the child wants to see the snake going from checkpoint u to checkpoint v. You may assume that all the wishes are distinct and correct. And the total number of wishes in any case is between 1 and 10000 (inclusive).
For each case, print the case number and 'YES' if it's possible, otherwise print 'NO'.
Sample Input |
Output for Sample Input |
2 2 2 0 9 9 10 1 10 15 1 2 0 9 0 11 |
Case 1: YES Case 2: NO |
Developed and Maintained by
JANE ALAM JAN |
Copyright © 2012
LightOJ, Jane Alam Jan |