Mr. X is developing an interactive question answer system. This system has the following features:
1. User will create a question answer journey.
2. Each journey will have a set of questions.
3. Each question will have one or many options.
4. Next question will come on the basis of user’s option selection.
When he was testing his system, he found that for some journey, he is unable to finish his journey and it goes on and on. So he wants to ignore those journeys, if the journey has any possibility to go on and on. He wants you to help him to decide whether the particular journey is valid or not.
Input
The first input is an integer T (1 ≤ T ≤ 100), denoting the number of journeys.
For each test case, the 1st line will contain n(1<=n<=100000) number of questions in that journey. Each question will have id from 1 to n. 1 will always be the starting question.
Next you will get the information of each question.
Each line will contain the number of options o(1<=o<=100000) for each question and followed by o numbers ai(1<=ai<=n or ai = -1, 1<=i<=o), ai-th question will come, if he choose the i-th option. The journey will end if ai = -1 is selected.
Output
For each case, print the journey number and if the journey is valid print “Valid” otherwise “Not Valid” without quote. See the sample input output for better understanding.
Sample
| Input | Output |
|---|---|
2 4 2 2 3 2 3 4 2 4 -1 2 -1 -1 4 2 2 3 2 3 4 2 4 -1 2 1 -1 | Case 1: Valid Case 2: Not Valid |
