Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Q/A Loop

By math10 · Limits 1s, 512 MB

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

InputOutput
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

    Discussion

    Statistics


    80% Solution Ratio

    alamkhanEarliest, 1M ago

    TurinhstuFastest, 0.1s

    insane_curiousLightest, 6.0 MB

    Iftekhar_HakimShortest, 1043B

    Submit

    Login to submit

    Editorial

    If we igone the -1 and created a directed graph with 1 as a root. We just need to check is there an...