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
cpchef7:
20220124 21:21:54
AC in one go, BFS will make it in one go 

princemishra:
20210309 06:39:07
apply simple bfs after sorting the edge list 

nathanaxel:
20200327 20:31:27
bruh i keep getting wa; I have collected 28 wa alr from this qn


ajkdrag:
20190701 09:26:19
The time limit is too small for java submissions, i think. Getting TLE and no test cases on SPOJTOOLKIT as well. 

eagleshadow:
20190517 00:18:47
just sort the edge list, before starting simple bfs :) 

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). 
Added by:  Surya Kiran 
Date:  20130905 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Codeblitz4 