1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*todo: add optimization 1*/
#include <cstdio>
#include <cstring>
#include <vector>
const int MAXN = 1000;
std::vector<int> edges[MAXN + 1];
bool visited[MAXN + 1];
/*stores the vertex matches it, 0 for not matched*/
int matched[MAXN + 1] = {0};
bool find_path(const int &x) {
    std::vector<int>::iterator it, it2;
    for (it = edges[x].begin(); it != edges[x].end(); ++it) {
        if (!visited[*it]) {
            visited[*it] = true;
            if (!matched[*it] || find_path(matched[*it])) {
                matched[x] = *it;
                matched[*it] = x;
                return true;
            }
        }
    }
    return false;
}
int main(void) {
    int n, m, u, v, match_count = 0;
    scanf("%d%d", &n, &m);
    while (m--) {
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX