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$。