MAKETREE - Hierarchy

no tags 

A group of graduated students decided to establish a company; however, they don't agree on who is going to be whose 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 Ath 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 Ath 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 2
1 3
2 3 4

Output:
2
0
1
2
Input:
7 4
2 2 3
1 6
1 7
2 1 2

Output:
4
1
1
0
4
2
3

hide comments
assemmedhat: 2024-05-07 10:01:21

this problem is made for topological sorting only. other solutions could workout,but i believe the answers are bound to the output of the topological sorting algorithm only.

Last edit: 2024-05-07 10:02:01
krytal: 2023-08-05 11:08:26

holy the topological sort =))

bechovang: 2023-06-17 13:18:43

the main boss can be any student (dont need to be a successfull student)

gebraiel: 2023-06-07 14:17:56

In test case 2 how the employee number 4 is the boss of 1 and 5 while in the wishes he wanted to be the boss of 1 and 2 not 5 ?

koree013: 2023-02-21 16:38:21

Leam

god_ert: 2022-01-08 21:13:24

can anyone tell me why my solution is wrong [id- 28977904]?

n_a_b_h_a_n: 2020-10-04 08:53:36

Why doesn't DSU work in this problem ? Or if does how so ?

Last edit: 2020-10-04 09:16:28
hafiz_: 2020-08-20 19:46:41

The problem statement has no vague at all.
The problem is a good application of topological sort. To get a better and easy to understand idea one should visit cp-algorithm's blog.

nguyenvietan: 2020-07-26 12:00:42

topological sort.

i_am_p0tat0: 2020-07-24 12:05:42

Can someone check my submission : 26325722? I'm not sure where I'm going wrong.


Added by:Adrian Satja Kurdija
Date:2011-04-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem