100 #P1165. *【一般图:最大匹配】带花树算法[scy]

*【一般图:最大匹配】带花树算法[scy]

【题意】

nn 个只牛进行一对一的匹配,求牛群最大匹配对数(没有分公牛和母牛,关系特别混乱的说)。

【输入格式】

第一行三个整数 n m(1n1040m105)n \ m( 1 \le n \le 10^4,0 \le m \le 10^5)

下来 mm 行,每行两个整数 x yx \ y,表示 牛xx 和 牛yy 互相喜欢,可以匹配。

【输出格式】

一行一个整数,表示牛群匹配对数最大值

7 6
1 3
4 2
4 5
4 3
4 6
6 7
3
28 32
1 2
2 3
4 5
5 10
5 8
6 14
6 7
3 6
3 4
7 9
8 9
10 28
10 11
11 13
11 12
12 13
13 16
14 15
15 20
15 18
16 17
17 24
17 22
18 26
18 19
19 21
20 21
22 23
23 26
24 25
25 27
26 27
14