PFDEP - Project File Dependencies


Project managers, such as the UNIX utility make, are used to maintain large software projects made up from many components. Users write a project file specifying which components (called tasks) depend on others and the project manager can automatically update the components in the correct order.

Problem

Write a program that reads a project file and outputs the order in which the tasks should be performed.

Input

For simplicity we represent each task by an integer number from $1, 2, \ldots, N$ (where $N$ is the total number of tasks). The first line of input specifies the number $N$ of tasks and the number $M$ of rules, such that $N \le 100$, $M \le 100$.

The rest of the input consists of $M$ rules, one in each line, specifying dependencies using the following syntax:

$T_0$ $k$ $T_1$ $T_2$ $\ldots$ $T_k$

This rule means that task number $T_0$ depends on $k$ tasks $T_1, T_2, \ldots, T_k$ (we say that task $T_0$ is the target and $T_1, \ldots, T_k$ are dependents).

Note that tasks numbers are separated by single spaces and that rules end with a newline. Rules can appear in any order, but each task can appear as target only once.

Your program can assume that there are no circular dependencies in the rules, i.e. no task depends directly or indirectly on itself.

Output

The output should be a single line with the permutation of the tasks $1 \ldots N$ to be performed, ordered by dependencies (i.e. no task should appear before others that it depends on).

To avoid ambiguity in the output, tasks that do not depend on each other should be ordered by their number (lower numbers first).

Example

Input:
5 4
3 2 1 5
2 2 5 3
4 1 3
5 1 1

Output:
1 5 3 2 4

hide comments
caro_linda2018: 2019-02-09 20:57:40

kshubham02, yeah, i missed that... Cost me a WA

ayushgupta1997: 2018-06-02 19:22:42

Same as http://www.spoj.com/problems/TOPOSORT/ kahn's mandatory!
Read this paper :http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/0695-19.pdf

tusharjape: 2018-05-09 12:10:54

What should be the answer to the test case?
Input:
9 4
1 4 2 3 4 5
4 1 6
3 1 7
5 1 9
Would it be? 2 7 3 6 4 9 5 1 8
or 2 7 3 6 4 8 9 5 1

kaustavdutta14: 2017-10-20 21:46:36

Does anyone have a good test Case?

Last edit: 2017-10-21 01:00:46
burninggoku: 2017-09-28 09:00:12

can someone pls tell what is wrong with this code.... 20245962 (id no)..thanks in advanced

kshubham02: 2017-09-25 09:13:43

"To avoid ambiguity in the output, tasks that do not depend on each other should be ordered by their number (lower numbers first)."
SHOULD BE IN BOLD

aman_9899: 2017-06-14 23:04:07

nice problem
kahn's algo with priority queue..!!!

up79: 2017-06-10 14:42:18

brute force passed . i don't know how but my solution is working in 0.00 sec .

Last edit: 2017-06-10 14:42:41
gboduljak: 2017-03-23 23:56:19

cool problem, hint : Kahn's algorithm

hasan356: 2017-02-07 10:27:02

my first topological !!


Added by:overwise
Date:2007-10-04
Time limit:0.405s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM ICPC -- SWERC 2001