UOJ Logo Zijian Online Judge

ZOJ

#9. 拓扑排序

Statistics

绵羊送给小喵喵了 $n$ 个小鱼干。小喵喵要把它们全部吃掉!

但是绵羊告诉小喵喵要按照某种顺序来吃。

绵羊一共说了 $m$ 条限制,每条限制的格式为 $u$ $v$ ,表示要先吃掉 $u$ 号小鱼干之后才能吃 $v$ 号小鱼干。

绵羊保证,这些条限制不会出现循环需求的情况,即一定存在某种顺序使得 $n$ 个小鱼干都被吃掉。

绵羊还允许小喵喵不遵守其中小于等于 $k$ 条限制。

小喵喵想知道在吃完所有的小鱼干的前提下,吃小鱼干的顺序的字典序最小是多少。

两个吃小鱼干的顺序的字典序大小比较即为:首先比较第一个吃的小鱼干,编号较小的字典序较小,若相同,则比较第二个吃的小鱼干,一直比到可以分出大小。

注意到两个顺序一定可以比较大小。

输入格式

第一行为 $3$ 个整数 $N、M、K$。

第二行至第 $M+1$ 行每行两个正整数 $u_i、v_i$,表示 $u_i$ 和 $v_i$ 有限制关系,即 $u_i$ 要比 $v_i$ 先吃。

输出格式

仅一行 $N$ 个正整数,为最优的吃小鱼干的顺序,相邻两个整数之间以空格隔开。

样例

input

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

output

1 5 4 3 2

限制与约定

对于 $30\texttt{%}$ 的数据,$1 \leq N、M \leq 8$。

对于 $60\texttt{%}$ 的数据,$1 \leq N、M \leq 20$。

对于另外 $30\texttt{%}$ 的数据,$K=0$。

对于 $100\texttt{%}$ 的数据,$1 \leq N、M \leq 152501$,$1 \leq u_i、v_i \leq N$,$0 \leq K \leq M$。

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载