TopCoder

User's AC Ratio

93.1% (310/333)

Submission's AC Ratio

33.4% (568/1700)

Tags

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 1

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

Sample Output 1

Yes
No

Hints

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

Problem Source

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

Subtasks

No. Testdata Range Score
1 0 50
2 1 50

Testdata and Limits

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