隨著錙殾梔枒到了尾聲,在作業分組、討論分組、比賽分組的情況下,眾多參與者之間也難免產生了一些情愫 (!?)。某位講師偷偷發現了這些事情,因此他默默地調查了每個人「有興趣」的對象,如果某兩個人彼此有興趣,就稱他們為一對「卦源」。不過講師很忙,忙中多錯,很快地另一位講師發現,有些結果可能有點……奇妙,舉例來說,$A$ 和 $B$ 是一對卦源,$B$ 和 $C$ 是一對卦源,但 $A$ 和 $C$ 又是一對卦源,這……
因此這位除錯講師決定要寫一個程式,給定所有對卦源,程式必須判定基於所有成員都是異性戀的假設下,輸入的資料是否「怪怪的」?即,在假設只有一男一女可形成卦源的情況下,調查的結果有沒有可能是合理的呢?
輸入的第一行包含一個正整數 $T (T \leq 10)$,代表測試資料的個數。每組測試資料的第一列有一個正整數 $n(1 < n \leq 10^5)$ 代表參與者的數目。第二列有一個正整數 $m(1\leq m \leq 2\times 10^5)$ ,代表卦源對數。接下來的 $m$ 列每列有 $2$ 個整數,代表每對卦源的組成成員代號。這 $n$ 個成員的代號分別從 $0$~$n-1$ 依序編號。
對每一組測試資料,輸出此調查基於假設情況下是否可能合理。若可能請輸出:NORMAL.
,否則請輸出:RAINBOW.
NEOJ Problem 1101
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~2 | $1\leq n\leq 10$ | 30 |
2 | 0~5 | $1\leq n\leq 1000$ | 30 |
3 | 0~9 | 無額外限制 | 40 |