DIGOKEYS  Find the Treasure
A psychic locklover called Digo likes playing games with Locks and Keys and also has very good logic.
One day he buys a set of N boxes, each of them has an index between {1, N} (inclusive) and no two boxes have same index. There is a key inside every box except the Nth box which has great treasure. He eventually finds out that due to a defect in the manufacturing of the keys, most of them could open more than one box.
The rule is that you are allowed to open only one box with any key. Each box except the first is locked. Now as Digo couldn’t wait long to acquire that great treasure he requests you to find a method to open the last box starting with the key in the first box with minimum number of steps.
INPUT
In first line, T no. of test cases.
For every test case:
In first line, there is an integer N : (number of locks)
In next N1 lines, on the i’th line there is an integer Mi the number of boxes which the key present in the i’th box can open. It is followed by the Mi integers (the indices of those boxes that can be opened by the key present in i’th box).
OUTPUT
For every test case:
one integer q, minimum number of boxes opened.
In the next line : the indices of the boxes opened in order separated by space. If there are many solutions print the one which is lexicographically smallest.
If there is no way to reach the last box print “1”.
Each test case is to be followed by a blank line.
Constraints
1 <= T <= 10
2 <= N <= 100000
1 <= Mi <= 10
Sample Input
2
3
1 2
1 3
4
2 2 3
1 1
2 2 4
Sample Output
2
1 2
2
1 3
hide comments
suyashky:
20190208 18:08:12
Make sure to store neighbours in lexicographical/sorted manner to avoid WA and break from bfs when you reach box with treasure to avoid TLE Last edit: 20190209 06:44:29 

smso:
20180926 08:57:35
beware that there are no testcases on spojtoolkit for this problem Last edit: 20190328 06:53:56 

terhesbalazs:
20171124 00:33:38
Can anyone solve this in Java? It exits always with Time Limit Exceeded error ... 

vengatesh15:
20170324 07:11:37
easy one with queue... 

oswald:
20131103 23:15:50
More testcases please. Getting WA on testcase(4). 

Mitch Schwartz:
20130905 21:57:12
Judge is "Ignores extra whitespaces", right?

Added by:  Surya Kiran 
Date:  20130905 
Time limit:  0.112s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Codeblitz4 