DZY Loves Topological Sorting

Time Limit: 2000ms
Memory Limit: 131072KB
This problem will be judged on HDU. Original ID: 5195
64-bit integer IO format: %I64d      Java class name: Main

Description

A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge $(u\rightarrow v)$ from vertex $u$ to vertex $v$, $u$ comes before $v$ in the ordering.
Now, DZY has a directed acyclic graph(DAG). You should find the lexicographically largest topological ordering after erasing at most $k$ edges from the graph.

Input

The input consists several test cases. ($TestCase\leq 5$)
The first line, three integers $n,m,k(1\leq n,m\leq 10^5, 0\leq k\leq m)$.
Each of the next $m$ lines has two integers: $u,v(u\not= v, 1\leq u,v\leq n)$, representing a direct edge$(u\rightarrow v)$.

Output

For each test case, output the lexicographically largest topological ordering.

Sample Input

5 5 2
1 2
4 5
2 4
3 4
2 3
3 2 0
1 2
1 3

Sample Output

5 3 1 2 4
1 3 2

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .