MAKETREE  Hierarchy
A group of graduated students decided to establish a company; however, they don't agree on who is going to be who's boss.
Generally, one of the students will be the main boss, and each of the other students will have exactly one boss (and that boss, if he is not the main boss, will have a boss of his own too). Every boss will have a strictly greater salary than all of his subordinates  therefore, there are no cycles. Therefore, the hierarchy of the company can be represented as a rooted tree.
In order to agree on who is going to be who's boss, they've chosen K most successful students, and each of them has given a statement: I want to be the superior of him, him, and him (they could be successful or unsuccessful). And what does it mean to be a superior? It means to be the boss, or to be one of the boss' superiors (therefore, a superior of a student is not necessary his direct boss).
Help this immature company and create a hierarchy that will satisfy all of the successful students' wishes. A solution, not necessary unique, will exist in all of the test data.
Input
In the first line of input, read positive integers N (N ≤ 100 000), total number of students, and K (K < N), the number of successful students. All students are numbered 1..N, while the successful ones are numbered 1..K.
Then follow K lines. In A^{th} of these lines, first read an integer W (the number of wishes of the student A, 1 ≤ W ≤ 10), and then W integers from the range [1, N] which denote students which student A wants to be superior to.
Output
Output N integers. The A^{th} of these integers should be 0 if student A is the main boss, and else it should represent the boss of the student A.
Example
Input:
4 2Output:
1 3
2 3 42
0
1
2
Input:7 4Output:
2 2 3
1 6
1 7
2 1 24
1
1
0
4
2
3
hide comments
n_a_b_h_a_n:
20201004 08:53:36
Why doesn't DSU work in this problem ? Or if does how so ?


hafiz_:
20200820 19:46:41
The problem statement has no vague at all.


nguyenvietan:
20200726 12:00:42
topological sort. 

i_am_p0tat0:
20200724 12:05:42
Can someone check my submission : 26325722? I'm not sure where I'm going wrong. 

nithish0201_:
20200713 19:41:33
. Last edit: 20200713 20:23:43 

predator00_:
20200609 21:02:24
just use topological sort blindly:) 

tikli_10:
20200605 13:51:12
Use iterative topological sort, not recursive 

Amr:
20200429 23:39:08
There are multiple valid solutions for this problem, Don't bind yourself with the answers in the test cases Last edit: 20200429 23:39:34 

nadstratosfer:
20200203 00:14:30
Not sure if TL was changed but as of now even pure Python gets AC. Nice problem. 

bigshakey:
20191110 18:05:25
Really struggling to get under the time limit in c++ Last edit: 20191110 18:05:42 
Added by:  Adrian Satja Kurdija 
Date:  20110415 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  own problem 