TopCoder

User's AC Ratio

85.7% (6/7)

Submission's AC Ratio

58.8% (10/17)

Tags

Description

近年來,由於各式各樣的升學壓力,幾乎很多家長們都會把孩子送到補習班裡面去學習,增加孩子們的競爭力。當然,今年也不例外。NPSC (Nobel Prize So Cool) 就是在這樣的環境底下成立的一個補習班。它打著培養孩子們發展科學和資訊能力結合的潛力,美其名『諾貝兒程式設計練才專班』,實際上卻是專門招收有才華的學生把他們組成一隊一隊的送進NPSC來比賽的可怕組織。

當然,經營了兩、三年後,經歷了各式各樣口碑的考驗,成功在補習業界闖出一片天。隨著大家口耳相傳,來報名的家長和孩子們也越來越多,今年甚至有多達近萬名的家長帶著學生來報名。因此,NPSC為了應付如此龐大的報名熱潮,做出了以下三點規範:

其一,今年特別規劃『家長排隊區』專門讓家長們排隊,如此一來孩子們便可以省下排隊的時間,專心寫程式。

其二,每一位家長必須一次幫兩位孩子報名,因為這樣補習班才能夠收到兩份的報名費用。如果出現了重複報名的現象,就視同報名失敗。

其三,如果報名失敗了,本年度將不得再度報名。

在某間高中的程式設計社裡面,有N個成員,他們決定今年一起報名NPSC,目標是打進決賽。於是他們找了M個路人,打算請這些路人幫忙排隊報名。不過為了避免有人報不到名,或者重複報名,每個路人都只會幫兩個成員排隊。你很湊巧地,是這個程式設計社當中的副社,而這個社團的社長早就已經寫ACM寫到完全忘我的境界了,重責大任於是落在你的身上。因此你很想知道,是不是真的能夠從這M個路人中請一些人出來排隊,最終能夠讓所有的N名成員都成功地報名了 NPSC練才專班。你很開心地寫了一個程式讓它放著慢慢跑,然後開心地跑去睡覺了。

不過你做了一個夢。
在夢境中,費盡了千辛萬苦,終於,從這M個路人裡面挑了一些人請他們幫忙排隊報名。但是,這些人裡面有人卻出現了不平之鳴。「為什麼是我要排隊?」「我比較想在家裡看電視啦!」「早知道就不幫忙出主意了!」「如果我沒有幫忙的話,明明有別種方案的啊,為什麼要找我!」

你驚醒。
你快速地檢查了程式,它還在慢跑,一點回應也沒有。你擔心,如果除了從這M個路人中找出某些人幫忙以外,如果還存在著另外一種讓N名成員都報名成功的方案,那麼這些人可能會吵架,會壞了大事的,因此這樣的報名方案不算是順利完成。換句話說,就像是36+45=79一樣,如果解法不是唯一的,那麼勢必會有很多人感到新奇、溫馨、誇張、難過、實用、高興、無聊,或者生氣。

「這真是個盲點呀華生!」

你大夢初醒。決定趕快生出一份程式,判斷到底有沒有辦法從這M個路人裡面唯一地找出一些人讓他們可以很順利地幫社團全部的N名成員完成報名呢?

Input Format

輸入的第一行包含一個正整數T代表測試資料的筆數。

接下來的每一筆測試資料,其第一行包含兩個正整數N, M依序代表社團的人數和路人的個數(1<=N<=1000, 0<=M<=10000)。而社團當中的成員也被編號為1, 2, …, N。

接下來有M行,每一行有兩個數字Ai, Bi,代表第i個路人想要幫社團裡面編號為Ai和Bi的兩名成員一起報名補習班。對於所有的i,Ai不會等於Bi。

Output Format

對於每一筆測試資料,如果不管怎麼挑路人都無法達成目標的話,請輸出NO。否則請輸出YES,而且要輸出那唯一的一種報名方案。

每一行輸出以一個空白隔開的兩個數字a, b(其中a < b),代表有某個路人會幫編號為a, b的兩名成員一起報名。請將這些數對由小到大輸出,也就是說,如果a, b比c, d還要早輸出,那麼一定有a < c。

Sample Input 1

2
4 4
1 2
2 3
3 4
4 1
4 3
1 2
2 3
3 4

Sample Output 1

NO
YES
1 2
3 4

Hints

Problem Source

原TIOJ1690 / NPSC2009決賽(prob H)

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1500 65536 262144 1