151 . 陣線推進
TopCoder
Description
如果你有玩過策略遊戲，尤其是 AOC，的話，一定曉得「戰線」是一種很重要的概念。大致上這概念可以這樣說明：如果對方設置陣地得宜，那麼在攻破某些陣地之前，一定要先攻破某些陣地，否則會導致我軍不是被城牆擋住，就是會被兩邊夾擊、全軍覆沒。
一般來說兩個玩家單挑對決時，因為通常都是互相快攻，彼此的陣地都還只有本陣，這方面問題就不大；但是當玩家數量變多，例如變成 4v4 團體戰的時候，隨著遊戲時間增常，陣地之間的關係也容易變得非常複雜，想攻破 $A$ 要攻破 $B$ 和 $C$、想攻破 $B$ 又要先攻破 $D$ 和 $E$ 等等。為了避免兵力的大幅損傷，你派出了大量的斥候犧牲小我完成大我，先確認了各個陣地的配置以及位置，接著便是擬定作戰計畫的時候了。如果已經知道要攻破某個陣地前要先攻破哪些陣地，你能否給出一個方案使得根據這個方案進行陣地攻略可以滿足所有要求條件、在全程都不腹背受敵的情況下與對方決一死戰呢？
Input Format
輸入的第一行是一個正整數 $T(T \leq 5)$。接下來會有 $T$ 組測試資料，每組測試資料的第一行是兩個非負整數 $n,m$，分別代表陣地的數量與陣地間的依賴關係數量；第二行到第 $m+1$ 行每行由兩個整數 $a$ 和 $b$ ($0 \leq a,b \leq n-1$)組成，代表要攻破陣地 $b$ 之前必須先攻破陣地 $a$，其中陣地從 $0$~$n-1$依序編號。
$1 \leq n \leq 100000$、$0 \leq m \leq 300000$
Output Format
如果存在題目所要求的方案，為了方便起見請輸出字典序最小的一個。(對於兩個不相等的序列 $X = \{X_1,X_2,...,X_k\}$ 與 $Y = \{Y_1,Y_2,...,Y_l\}$，我們說序列 $X$ 的字典序比 $Y$ 小當且僅當「存在 $i(1 \leq i \leq min(k,l))$ 滿足對於所有的 $j$ 滿足 $1\leq j < i$ 都有 $X_j = Y_j$，且$X_i < Y_i$」。反之則說序列 $X$ 的字典序比 $Y$ 大。兩個序列的字典序相同當且僅當兩個序列相同。)否則代表一場喋血的戰役在所難免，只好輸出"QAQ"(不含引號)了。
Sample Input 1
3 3
0 1
1 2
0 2
3 3
0 1
1 2
2 0
Sample Output 1
QAQ
Hints
請相信只輸出QAQ不會拿到任何分數
Problem Source
NEOJ Problem 165
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~3 | $1 \leq n \leq 1000$、$0 \leq m \leq 20000$ | 40 |
| 2 | 0~9 | 無額外限制 | 60 |