DIGOKEYS - Find the Treasure

no tags 

A psychic lock-lover 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.


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 N-1 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).


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.


1 <= T <= 10

2 <= N <= 100000

1 <= Mi <= 10

Sample Input



1 2

1 3


2 2 3

1 1

2 2 4

Sample Output


1 2



1 3

hide comments
cpchef7: 2022-01-24 21:21:54

AC in one go, BFS will make it in one go

princemishra: 2021-03-09 06:39:07

apply simple bfs after sorting the edge list

nathanaxel: 2020-03-27 20:31:27

bruh i keep getting wa; I have collected 28 wa alr from this qn

ajkdrag: 2019-07-01 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: 2019-05-17 00:18:47

just sort the edge list, before starting simple bfs :)

suyashky: 2019-02-08 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: 2019-02-09 06:44:29
smso: 2018-09-26 08:57:35

beware that there are no testcases on spojtoolkit for this problem

Last edit: 2019-03-28 06:53:56
terhesbalazs: 2017-11-24 00:33:38

Can anyone solve this in Java? It exits always with Time Limit Exceeded error ...

vengatesh15: 2017-03-24 07:11:37

easy one with queue...

oswald: 2013-11-03 23:15:50

More testcases please. Getting WA on testcase(4).

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