Submission #2560876

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100000 + 10;

struct Edge {
    int v, n;
} e[MAXN << 1];
int G[MAXN], edgeCnt;

void _add_edge(int u, int v)
{
    e[++edgeCnt].n = G[u];
    G[u] = edgeCnt;
    e[edgeCnt].v = v;
}

void add_edge(int u, int v)
{
    _add_edge(u, v);
    _add_edge(v, u);
}

int n, m;
int f[MAXN];
int g[MAXN];
int h[MAXN];
int size[MAXN];

bool vis[MAXN];
int foo, bar;

void dfs1(int u, int fa)
{
    size[u] = f[u] ? -1 : 1;
    size[u] += f[u] ? -h[u] : h[u];
    for (int i = G[u]; i; i = e[i].n)
        if (e[i].v != fa) {
            if (u == bar && e[i].v == foo
                || u == foo && e[i].v == bar) {
                    continue;
            }
            f[e[i].v] = f[u] ^ 1;
            dfs1(e[i].v, u);
            size[u] += size[e[i].v];
            g[u] += g[e[i].v];
        }
}

bool dfs2(int u, int fa)
{
    if (vis[u])
        return false;
    vis[u] = true;
    for (int i = G[u]; i; i = e[i].n)
        if (e[i].v != fa) {
            if (!dfs2(e[i].v, u))
                foo = u, bar = e[i].v;
        }
    return true;
}

int main()
{
    // freopen("sapphire.in", "r", stdin);
    // freopen("sapphire.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
    }
    if (m == n - 1) {
        dfs1(1, -1);
        long long ans = 0;
        for (int i = 1; i <= n; ++i)
            ans += abs(size[i]);
        cout << (size[1] == 0 ? ans : -1) << endl;
    } else {
        dfs2(1, 0);
        g[foo] = 1;
        g[bar] = -1;
        dfs1(1, 0);
        long long ans = 0;
        if (f[foo] == f[bar]) {
            if (abs(size[1]) & 1)
                cout << "-1\n";
            else {
                ans += abs(size[1]) / 2;
                h[foo] = h[bar] = ans;
                for (int i = 1; i <= n; ++i)
                dfs1(1, 0);
                cout << ans << endl;

            }
        } else {
            if (size[1] != 0)
                cout << "-1\n";
            else {
                static int a[MAXN], cnt = 0;
                for (int i = 1; i <= n; ++i) {
                    if (g[i] == 0) {
                        ans += abs(size[i]);
                    } else {
                        a[++cnt] = -g[i] * size[i];
                    }
                }
                nth_element(a + 1, a + (1 + cnt) / 2, a + cnt + 1);
                int temp = a[(1 + cnt) / 2];
                for (int i = 1; i <= n; ++i)
                    if (g[i] != 0) {
                        ans += abs(size[i] + g[i] * temp);
                    }
                ans += (f[foo] ^ 1 ? -1 : 1) * temp;
                cout << ans << endl;
            }
        }
    }
}

Submission Info

Judge Result