小寶的著色問題 (AP325 Q-7-8)

小寶有個布娃娃，娃娃會變化。娃娃身上有一些圖案，這些圖案是由一些圓圈和一些線條組成，每個線條連接著某兩個不同的圓圈。小寶很喜歡著色，他決定要把這些圓圈塗上紅色或藍色，他覺得有線條相連的圓圈最好塗上不一樣的顏色，但是因為圓圈很多，他不知道能不能夠完成這樣的想法，請你幫他計算看看是否可以有辦法完成這樣的著色。

輸入格式

第一行有一個整數 \(T\)，代表接下來有 \(T\) 張圖的資料要計算。每張圖資料的第一行是兩個整數 \(n\) 與 \(m\)，代表有 \(n\) 個圓圈與 \(m\) 個線條；第二行有 \(2m\) 個整數，每兩個一組代表一根線條所連接的兩個圓圈編號，圓圈是以 \(0 \sim n-1\) 編號（若 \(m = 0\)，這張圖就沒有第二行）。

限制

• \(1 \le T \le 20\)。
• \(1 \le n \le 10^4\)，\(0 \le m \le 10^5\)。
• 每根線條連接的兩個圓圈編號不同；同一對圓圈之間可能有多根線條。

輸出格式

依序每一行輸出一張圖是否可以正確著色，如果是，則輸出 yes，否則輸出 no。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入

2
2 0
4 3
0 3 3 2 2 0

範例輸出

yes
no

範例說明

第一張圖 \(n = 2\)、\(m = 0\)，表示有兩個圓圈而沒有線條，可以正確著色。第二張圖有 \(4\) 個圓圈與 \(3\) 根線條，\(3\) 根線條是 \((0, 3)\)、\((3, 2)\) 與 \((2, 0)\)，這 \(3\) 個點如果只用 \(2\) 種顏色，不管如何上色都會有同色的相連。

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 7 章 Q-7-8，第 247 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。