TopCoder

Thumb mikasa mikoto furikae
Omelet
ㄏ一ㄏ一 $$AC \approx (111111111)_2$$

User's AC Ratio

95.8% (23/24)

Submission's AC Ratio

82.6% (38/46)

Description

  在大不列顛軍中有所謂的搭擋制度,通常是由老兵搭配新兵,而且一個老兵只能搭配一個新兵,新兵亦同。

  但也有人之間根本無法溝通,所以無法搭擋。

  現在給你一些老兵與新兵的能否搭擋的關係表,請問最多可以湊出多少搭擋?

Input Format

只有一組測試資料。

第一行為兩個數字,n,m分別代表有幾個老兵與新兵(也就是老兵新兵人數都為n) 以及幾對人之間可以互相搭擋。

(0≦n≦10,0≦m≦100)

接著有m行,每行有兩個數字,x,y,代表老兵x與新兵y搭擋。

(0≦x,y≦n-1)

Output Format

輸出最好的情形能有幾對搭擋。

Sample Input

3 4
0 0
0 2
1 1
2 1

Sample Output

2

Hints

※2008/07/10 測資敘述修正 by ggm,感謝 shik。

Problem Source

原TIOJ1376 / 快樂暑假營第二次練習比賽。
(Maximum Matching Problem) Problem Setter:ggm

Subtasks

No. Testdata Range Score
1 0 50
2 1 50

Testdata and Limits

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