TopCoder

Cheng0928
笨笨的笨蛋 $\huge \color{red}{I'm\ Stupid. How\ to\ AC?}$

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

85.7% (6/7)

Tags

Description

隨著錙殾梔枒到了尾聲,在作業分組、討論分組、比賽分組的情況下,眾多參與者之間也難免產生了一些情愫 (!?)。某位講師偷偷發現了這些事情,因此他默默地調查了每個人「有興趣」的對象,如果某兩個人彼此有興趣,就稱他們為一對「卦源」。不過講師很忙,忙中多錯,很快地另一位講師發現,有些結果可能有點……奇妙,舉例來說,$A$ 和 $B$ 是一對卦源,$B$ 和 $C$ 是一對卦源,但 $A$ 和 $C$ 又是一對卦源,這……

因此這位除錯講師決定要寫一個程式,給定所有對卦源,程式必須判定基於所有成員都是異性戀的假設下,輸入的資料是否「怪怪的」?即,在假設只有一男一女可形成卦源的情況下,調查的結果有沒有可能是合理的呢?

Input Format

輸入的第一行包含一個正整數 $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$ 依序編號。

Output Format

對每一組測試資料,輸出此調查基於假設情況下是否可能合理。若可能請輸出:NORMAL.,否則請輸出:RAINBOW.

Sample Input 1

2
3
3
0 1
1 2
2 0
9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8

Sample Output 1

RAINBOW.
NORMAL.

Hints

Problem Source

NEOJ Problem 1101

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 262144 65536 1 2 3
1 3000 262144 65536 1 2 3
2 3000 262144 65536 1 2 3
3 3000 262144 65536 2 3
4 3000 262144 65536 2 3
5 3000 262144 65536 2 3
6 3000 262144 65536 3
7 3000 262144 65536 3
8 3000 262144 65536 3
9 3000 262144 65536 3