TopCoder

User's AC Ratio

96.0% (97/101)

Submission's AC Ratio

44.8% (233/520)

Description

給你一個圖(Graph),請問這個圖是否為一個二分圖(bipartite graph)?

所謂的二分圖,就是存在一種分法,把所有頂點分成兩個點集X和Y,其中X以及Y內部的頂點互不相鄰。

Input Format

輸入可能包含多筆測試資料。
每筆測試資料的第一列有兩個整數n,m(1<=n<=40,000;0<=m<=500,000),分別代表一個圖的點數和邊數。
點的編號是從1到n。
接下來有m列,每列有兩個以空白隔開的正整數,代表一條邊所連的兩個端點編號。
當n=m=0時代表輸入結束。

Output Format

對於每筆測試資料,若該圖是二分圖,請輸出Yes,否則輸出No。

Sample Input

3 2
1 2
2 3
3 3
1 2
2 3
3 1
0 0

Sample Output

Yes
No

Hints

※2008/08/25:題目敘述修正,感謝math120908。 by Tmt

Problem Source

原TIOJ1209 / TIOJ 2008例行賽03 (prob A)。經典問題練習。Problem Setter:Tmt。

Subtasks

For Testdata: 0 ~ 0, Score: 50
For Testdata: 1 ~ 1, Score: 50
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 262144
1 10000 65536 262144