1418 . 大型男芒果
TopCoder
Tags
Description
在水果王國裡面，有一個舉世公認的大型男芒果。因為他實在是太帥了，導致蔬菜王國與水果王國之間曾經為了爭奪芒果進行了長達幾十年的戰爭，史稱桃酪梨戰爭，但這又是另一個故事了。
因為芒果的追求者實在太多了，他決定乾脆當起月老。芒果現在有 $n$ 個追求者，而每個追求者除了芒果以外都可以和一些其他的追求者互相配對，但是每個追求者最多就只能和另一個追求者配對，請幫忙芒果算出在最好的情況下，最多能有幾對追求者配對成功。
Input Format
輸入第一行為兩個正整數 $n,m$ 代表有 $n$ 個芒果追求者和 $ m $ 種可能的配對關係
接下來 $m$ 行，每行有兩個正整數 $u,v$ 表示芒果追求者 $u$ 和芒果追求者 $v$ 可以被配對
- $1 \leq n \leq 500$
- $0 \leq m \leq 120000$
- $1 \leq u < v \leq n$
- 保證不會出現重複的 $u,v$
Output Format
輸出一個整數，表示最多可以配對幾對芒果追求者
Sample Input 1
7 8 1 3 1 6 6 7 2 7 1 2 2 4 4 5 2 5
Sample Output 1
3
Sample Input 2
5 4 1 2 1 3 1 4 1 5
Sample Output 2
1
Hints
芒果不僅是大型男，數學也很好，他留了一個他之前拿來算在 $\mathbb{F}_{P}$ 下的矩陣 rank 的程式給你 mango_rank1.cpp 。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資。 | 0 |
| 2 | 0~49 | 無特別限制。 | 100 |