# Bipartite Graph

## Matching

```#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;

vector<int> g[N];
int from[N], tot, use[N];
int color[N];
vector<int> leftSide;

bool match(int x) {
for (int v: g[x]) {
if (!use[v]) {
use[v] = 1;
if (from[v] == -1 || match(from[v])) {
from[v] = x;
return 1;
}
}
}
return 0;
}

int hungary() {
tot = 0;
memset(from, -1, sizeof from);
for (int u: leftSide) {
memset(use, 0, sizeof use);
if (match(u)) ++tot;
}
}

int colorit(int x, int c) {
if (use[x]) {
if (color[x] == c) return 0;
else throw 3;
} use[x] = 1;
color[x] = c;
for (int y: g[x]) {
colorit(y, c ^ 1);
}
return 0;
}

int main() {
int n; scanf("%d", &n);
int m; scanf("%d", &m);
for (int i = 1; i <= n; ++i)
g[i].clear();
for (int i = 0; i < m; ++i) {
int u, v; scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
memset(use, 0, sizeof use);
for (int i = 1; i <= n; ++i)
if (!use[i]) colorit(i, 1);
leftSide.clear();
for (int i = 1; i <= n; ++i)
if (color[i] == 1) leftSide.push_back(i);
int tot = hungary();
printf("%d\n%d\n", tot, n - tot);
return 0;
}
```