Original Description

殿壬是個天才兒童，他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲，而現在要講的，是殿壬兩歲又四個月大時的故事。

殿壬兩歲又四個月時，就致力於研究圖論（Graph Theory）中的「匹配問題」（Matching Problem）：給你一張圖 $G = (V,E)$ ，請問這張圖的最大匹配的邊的數量是多少。

如果你不知道什麼是「匹配問題」的話，沒有關係，殿壬已經幫你查好維基百科了：對於一個給定的圖 $G=(V,E)$ ，這張圖的一個匹配 $M$ 是圖 $G$ 的一個子圖（由原來的圖的一部分頂點和一部分邊構成的圖），其中每兩條邊都不相鄰（沒有公共頂點）。在匹配圖中，一個頂點連出的邊數至多是一條。而一個匹配的大小，就是匹配圖 $M$ 裡面的邊的數量。

現在，殿壬遇到了一題匹配問題了：給你一張 $N$ 點（點從 $1$ 到 $N$ 編號） $M$ 邊（邊從 $1$ 到 $M$ 編號）的無向連通簡單圖（Simple Graph，不存在重邊、自環的圖），第 $i$ 條邊連結著點 $a_i$ 和點 $b_i$ ，請輸出最大匹配的邊的數量。

Original Input Format

輸入的第一行包含兩個正整數 $N, M$ ，代表圖的點數、邊數。

接下來的 $M$ 行，每行包含兩個正整數，第 $i$ 行的兩個正整數為 $a_i, b_i$ ，代表第 $i$ 條邊連接的邊。

• $1 \le N \le 100$
• $1 \le M \le 500$
• $1 \le a_i, b_i \le N$
• 保證圖是 連通 並且 簡單 （不存在重邊、自環）的

Original Output Format

請輸出一個數字，代表最大匹配的邊的數量。

Original Sample Input

Sample Input 1:
3 3
1 2
2 3
3 1

Sample Input 2:
4 3
1 2
2 3
3 4

Original Sample Output

Sample Output 1:
1

Sample Output 2:
2

Original Limits

• Time Limit: 2 second
• Memory Limit: 256 MB

Program To Be Hacked

#include <bits/stdc++.h>
using namespace std;

int n , m , u[106] , ans;
pair<int,int> x[506];

int main(){
    clock();
    cin >> n >> m;
    for(int i = 0 ;i < m; ++i) cin >> x[i].first >> x[i].second;
    for(int times = 0; times < 5000 * 5000; ++ times){
        random_shuffle(x , x + m);
        memset(u,0,sizeof(u));
        int cnt = 0;
        for(int i = 0 ;i < m; ++i) if(u[x[i].first] == 0 && u[x[i].second] == 0){
            u[x[i].first] = 1;
            u[x[i].second] = 1;
            cnt ++;
        }
        ans = max(ans , cnt);
        if(1.0 * clock() / CLOCKS_PER_SEC > 1.99) break;
    }
    cout << ans << endl;
    return 0;
}

Judge Method

精通「匹配問題」的殿壬，他發現：認真寫出一個 $O(n^ 3)$ 的縮花演算法太累了，不如好好的 唬爛 一波，寫個隨機演算法，正確的機率又高、程式碼又短，怎麼看都是一個好選擇。

你，身為殿壬的好朋友，決定要幫殿壬戒掉這個壞習慣，而讓他戒掉這個壞習慣的方法就是給他一筆會 Wrong Answer 的測試資料。

請你幫幫殿壬吧。

Sample Code

以下程式碼能產生本題合法但一定不會讓你得到 AC 的測試資料。

#include <cstdio>
int main() {
    printf("3 3\n1 2\n2 3\n3 1\n");
}