文件目录

// 二分图
// a+b= n
#include <bits/stdc++.h>
using namespace std;
// 邻接表
vector<int> e[100050];
int a, b, n, m, u, v, s1, s2;
int vis[100050];
void dfs(int x, int c)
{
    if (c)
        s1++; // 1色
    else
        s2++; // 0色
    for (int i = 0; i < e[x].size(); i++)
    {
        int v = e[x][i];
        if (vis[v] == -1)
        {
            vis[v] = !c;
            dfs(v, !c);
        }
    }
}
int main()
{
    memset(vis, -1, sizeof(vis));
    scanf("%d %d", &n, &m);
    while (m--)
    {
        scanf("%d %d", &u, &v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    // 深搜填色
    for (int i = 1; i <= n; i++)
    {
        if (vis[i] == -1)
        {
            s1 = 0, s2 = 0; // 统计
            vis[i] = 1;
            dfs(i, 1);
            // 非连通图累计
            if (s1 < s2)
            {
                a += s1;
                b += s2;
            }
            else
            {
                a += s2;
                b += s1;
            }
        }
    }
    cout << a << " " << b;
    return 0;
}