如果一個無向圖 (undirected graph) G 的頂點集合 (vertex set) 可被分割為兩個互不相交的非空子集 A 和 B，使得 G中每一條邊 (edge) 的兩個頂點分別屬於這兩個子集，那麼我們稱G 為一個「二分圖」 (bipartite graph)，並稱 A 和 B 是一個有效分割。例如： 圖一(a)是一個二分圖，因為我們可以取 A = {2, 3, 5, 9} 和 B = {1, 4, 6, 7, 8, 10, 11} 使得每一條邊的兩個頂點分別屬於 A 和 B；圖一(b)也是一個二分圖，因為 A = {1, 4, 6, 8, 11, 13} 和 B = {2, 3, 5, 7, 9, 10, 12} 是一個有效分割；圖一(c)則不是一個二分圖，因為不存在任何有效分割。
一個圖 G 是不是二分圖可以判斷如下。我們試著將 G 中的每一個頂點著上白色或黑色。為了方便說明，我們假設 G 是一個連通圖 (connected graph)，也就是說 G 中任兩個頂點間都存在一條路徑:而且我們稱白和黑是兩個對立的顏色。開始時我們任選一頂點著上白色，其餘所有頂點都沒有顏色。然後重複以下規則直到每一個頂點都被著上顏色：
(R) 挑一個有顏色的頂點，將所有和它相鄰的頂點著上對立的顏色。
在過程中如果發現一個已經有顏色的頂點因為 (R) 這個規則必須被著上不同的顏色，那麼就出現了矛盾，G 不是二分圖，可以停止著色。否則，可以看出在著色結束後，白和黑兩群頂點所代表兩個子集 A 和 B 是一個有效分割。
測試資料第一行有兩個數字 n, m ，第一個數字 n 表示圖中的頂點數， 1 < n ≤ 105 ，第二個數字 m 表示圖中的邊數， 1 ≤ m ≤ 106，接下來會有 m 行，每行有兩個正整數 i, j，i ≠ j，1 ≤ i ≤ n，1 ≤ j ≤ n，表示頂點 i 和 j 之間有一條邊。(不會有重複邊)
請輸出一行，如果給定的無向圖 G 不是一個二分圖，請輸出 0；如果給定的無向圖 G 是一個二分圖，請輸出最小的整數 k 滿足 G 存在一個有效分割 A 和 B，其中 A 中的頂點數是 k。
第二子題 輸入範例： 4 4 1 2 4 3 2 4 1 3 第三子題 輸入範例： 11 13 1 2 11 9 5 7 3 11 5 6 3 1 6 9 2 4 4 5 8 5 9 8 9 10 8 2 第四子題 輸入範例： 8 10 6 5 1 4 5 7 8 6 3 1 2 1 5 4 2 5 8 7 6 3 第五子題 輸入範例： 13 12 8 7 1 2 3 6 5 4 1 3 9 8 11 12 10 8 6 5 3 4 6 2 13 12
第二子題 輸出範例： 2 第三子題 輸出範例： 4 第四子題 輸出範例： 0 第五子題 輸出範例： 5
本題共有四個子題，每一子題可有多筆測試資料：
第一子題，n ≤ 3 且 G 是連通圖，解出可以獲得 15 分；
第二子題，n ≤ 4 且 G 是連通圖，解出可以獲得 15 分；
第三子題，n ≤ 104 且 G 是連通圖，解出可以獲得 40 分；
第四子題，n ≤ 104 (G 不一定是連通圖)，解出可以獲得 15 分；
第五子題，n ≤ 105 且 m ≤ 106 (G 不一定是連通圖)，解出可以獲得 15 分。