Maximizing Lexicographical Topological Sort

A permutation \(a_1, a_2, \ldots, a_n\) of \(1\) to \(n\) is called a topological sort of a directed acyclic graph (DAG) if for every directed edge \(u \to v\) the vertex \(u\) appears before \(v\) in the permutation. Among all topological sorts, the lexicographically smallest one is obtained by repeatedly choosing the smallest available source (a vertex with indegree zero).

You are given a DAG with \(n\) vertices and \(m\) edges together with an integer \(k\). You are allowed to add at most \(k\) extra directed edges, with the condition that after each addition the graph remains acyclic. The goal is to add these edges optimally so that the lexicographically minimal topological sort of the augmented graph is as large as possible (when compared lexicographically).

Hint: When there are multiple sources, the lexicographically smallest topological sort would normally pick the smallest vertex. To improve the ordering you can add extra edges from the largest source vertex to all the other source vertices. However, note that if there are \(s\) sources at a given step, you have to add \(s-1\) edges in order to force the largest available vertex to be the only source. If \(k\) is insufficient for this, then do not add any edge at that step.

Your task is to compute the final topological order after optimally adding at most \(k\) edges.

inputFormat

The input begins with a line containing three integers \(n\), \(m\) and \(k\) where \(n\) is the number of vertices, \(m\) is the number of edges, and \(k\) is the maximum number of extra edges you can add.

Then, there are \(m\) lines, each containing two integers \(u\) and \(v\) indicating a directed edge from vertex \(u\) to vertex \(v\).

You can assume that the given graph is a DAG.

outputFormat

Output a single line containing \(n\) space-separated integers which represent the lexicographically minimal topological sort of the graph after the optimal addition of extra edges.

sample

3 0 1

1 3 2