U715985 BX 的 Bug 依赖链 (BX's Bug Dependency Chain)
题目背景
BX 同学最近迷上了全栈开发,并亲手搭建了一个炫酷的个人网站 [CodeY](https://codey.cn.mt)。
然而网站刚一上线,就被热心的同学们(比如专抓漏洞的 JZ 和狂测试数据的 ZS)找出了漫天飞舞的 Bug。
BX 是一个**非常听劝且行动力极强**的人,别人只要指出一个 Bug,他就会立刻去修。
但随着修复工作的进行,BX 发现了网站架构中一个令人头疼的抽象设定:**Bug 之间居然存在依赖关系!**
比如,如果不先修复登录模块的 Bug,就根本无法复现并修复支付模块的 Bug。
由于 Bug 数量实在太多,网友们帮 BX 整理出了一份多达 $M$ 条的“Bug 依赖清单”。
题目描述
网站中总共有 $N$ 个已知 Bug,编号为 $1$ 到 $N$。
网友们提交了 $M$ 条依赖关系,每条依赖关系用一对整数 $(u, v)$ 表示,意味着**必须先修复编号为 $u$ 的 Bug,才能去修复编号为 $v$ 的 Bug**。
BX 是一个有强迫症的完美主义者。在所有“当前可以被修复的 Bug”中(即该 Bug 的所有前置 Bug 都已经被修复),他总是**优先选择编号最小的 Bug** 进行修复(编号越小说明暴露得越早,网友催得越急)。
请你编写程序,帮 BX 推导出一份完美的**修 Bug 顺序表**。
此外,由于网站代码可能是互相引用的“屎山”,依赖清单中可能会出现**死锁**(即循环依赖,比如修 A 需要先修 B,修 B 需要先修 C,修 C 又需要先修 A)。如果存在死锁导致 BX 无法修完所有的 Bug,请让他放弃挣扎,输出 `WTF`。
输入格式
第一行包含两个整数 $N, M$,分别表示 Bug 的总数和依赖关系的总数。
接下来 $M$ 行,每行包含两个整数 $u, v$,表示修复 Bug $v$ 的前置条件是修复 Bug $u$。(输入可能包含重边,但保证不会有自己依赖自己的情况)。
输出格式
如果可以修完所有的 Bug,输出一行 $N$ 个用空格分隔的整数,表示 BX 修复 Bug 的完美顺序。
如果存在死锁(循环依赖)导致无法修完所有 Bug,只需输出一行字符串 `WTF`。
说明/提示
**【样例解释 1】**
初始时,没有前置依赖的 Bug 是 3 和 5。BX 优先选择编号最小的 3 进行修复。
修完 3 后,4 的前置条件满足了,当前可修复的是 4 和 5。BX 选择 4。
修完 4 后,可修复的只有 5。BX 修 5。
修完 5 后,1 的前置条件满足了。BX 修 1。
修完 1 后,2 的前置条件全部满足(1 和 3 都修了)。BX 修 2。
最终顺序为:3 4 5 1 2。
**【样例解释 2】**
1 需要 3,3 需要 2,2 需要 1。陷入死锁循环,输出 `WTF`。
### 数据规模与约定
- 对于 $30\%$ 的数据,$1 \le N \le 1000$,$0 \le M \le 2000$。
- 对于 $100\%$ 的数据,$1 \le N \le 10^5$,$0 \le M \le 2 \times 10^5$,$1 \le u, v \le N, u \neq v$。