Problem : 369 - 3C. 壞掉的二分圖

Problem Statistics

Solved Member: 2　　Submission: 8　　User Tried: 2

Statement:

某天 Nekosyndrome 為了比賽在出二分圖測資，他依照以下的演算法來出測資：

1.決定一個 N,M，代表無向圖的點數和邊數，點由 1 標到 N
2.給每一個點 i 決定一個顏色白或者黑
3.隨便生出 M 條邊，每條邊連接的兩個點顏色都相異(一邊為白，一邊為黑)

然而，某次檢查測資的時候他發現他的程式有錯！這個 bug 會恰好生出一條邊連接兩個同色的點。

他想把生出來的測資中錯誤的那條邊給找出來，但是他發現測資裡面只有 N,M 以及 M 條邊，並沒有程式當初給每個點決定的顏色。

於是他開始想知道，每個測資裡面究竟是有幾條邊是「有可能」出錯的呢？

Input:Output:

第一行有兩個整數 N,M ，代表無向圖的點數和邊數。
接下來 M 行，每一行有兩個數字 Ai,Bi ，代表連接著點 Ai 和點 Bi 的兩條邊。

限制：
2 ≤ N ≤ 100000
1 ≤ M ≤ 200000
1 ≤ Ai,Bi ≤ N
沒有自環(Ai != Bi)

Subtask 1：(10分)
N ≤ 1000
M ≤ 2000

Subtask 2：(10分)
給的圖連通
N = M

Subtask 3：(35分)
給的圖連通
M ≤ N+100

輸出一個數字，代表有幾條邊是可能出錯的。

Sample Input:Sample Output:

SAMPLE A:
4 5
1 2
1 3
1 4
2 4
3 4

SAMPLE B:
4 4
1 2
2 3
3 2
4 3

SAMPLE C:
13 16
1 6
2 6
3 1
3 2
4 7
4 7
5 9
6 5
8 2
8 13
9 11
10 3
11 10
11 12
12 8
13 6

SAMPLE A:
1

SAMPLE B:
2

SAMPLE C:
3

HINT:

下圖中的顏色代表程式中"可能"的塗色方法

SAMPLE A: (1,4) 可能出錯

SAMPLE B: (1,2), (4,3) 為兩條可能出錯的邊

注意：依照題敘中的演算法，如果其中一條邊 (2,3) 是出錯的，代表在程式中 2,3 兩個點的顏色是相同的。
但是刪掉這條邊之後還剩下另一條未出錯的邊 (2,3)，出現矛盾。
因此兩條 (2,3) 都是沒有問題的邊

Source:

2013/2014 JOI 合宿 3模（日本IOI國手考）

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	500ms	262144kb
0-2	500ms	262144kb
0-3	500ms	262144kb
1-1	500ms	262144kb	10
1-2	500ms	262144kb
1-3	500ms	262144kb
1-4	500ms	262144kb
1-5	500ms	262144kb
1-6	500ms	262144kb
1-7	500ms	262144kb
1-8	500ms	262144kb
1-9	500ms	262144kb
1-10	500ms	262144kb
1-11	500ms	262144kb
1-12	500ms	262144kb
2-1	500ms	262144kb	10
2-2	500ms	262144kb
2-3	500ms	262144kb
2-4	500ms	262144kb
2-5	500ms	262144kb
2-6	500ms	262144kb
2-7	500ms	262144kb
2-8	500ms	262144kb
3-1	500ms	262144kb	35
3-2	500ms	262144kb
3-3	500ms	262144kb
3-4	500ms	262144kb
3-5	500ms	262144kb
3-6	500ms	262144kb
3-7	500ms	262144kb
3-8	500ms	262144kb
3-9	500ms	262144kb
3-10	500ms	262144kb
3-11	500ms	262144kb
3-12	500ms	262144kb
4-1	500ms	262144kb	45
4-2	500ms	262144kb
4-3	500ms	262144kb
4-4	500ms	262144kb
4-5	500ms	262144kb
4-6	500ms	262144kb
4-7	500ms	262144kb
4-8	500ms	262144kb
4-9	500ms	262144kb
4-10	500ms	262144kb
4-11	500ms	262144kb
4-12	500ms	262144kb
4-13	500ms	262144kb
4-14	500ms	262144kb
4-15	500ms	262144kb
4-16	500ms	262144kb
4-17	500ms	262144kb
4-18	500ms	262144kb