Submission #872661

---

Source Code Expand

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

#define forn(i,n) for(int i=0;i<(int)(n);i++)
#define si(c) ((int)(c).size())
#define forsn(i,s,n) for(int i = (int)(s); i<((int)n); i++)
#define dforsn(i,s,n) for(int i = (int)(n)-1; i>=((int)s); i--)
#define all(c) (c).begin(), (c).end()
#define D(a) cerr << #a << "=" << a << endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair

typedef long long int ll;
#define int ll
typedef vector<int> vi;
typedef pair<int,int> pii;

const int N = 2e5 + 10;

int n,m;
vi adj[N];

bool vis[N];
int pre[N], a = -1,b;
void dfs_cycle(int u, int p) {
    vis[u] = true;
    pre[u] = p;
    for (int v : adj[u]) if (v != p) {
        if (vis[v]) {
            if (a == -1) {
                a = v; 
                b = u;
            }
        }
        else dfs_cycle(v,u);
    }
}

vi cycle;
bool cyc[N];
void build_cycle() {
    for (int x = b; x != -1; x = pre[x]) {
        //cerr << x << ' ' << pre[x] << endl;
        cyc[x] = true;
        cycle.pb(x);
        if (x == a) break;
    }
}

ll res = 0;
int bal[N];
void dfs(int u, int p) {
    bal[u] = 1;
    for (int v : adj[u]) if (!cyc[v] && v != p) {
        dfs(v,u);
        bal[u] -= bal[v];
    }
    if (p != -1) res += abs(bal[u]);
}

void result(ll res) {
    cout << res << '\n';
    exit(0);
}

#undef int
int main() {
#define int ll
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    memset(vis,0,sizeof vis);
    memset(cyc,0,sizeof cyc);

    cin >> n >> m;
    forn(_,m) {
        int u,v; cin >> u >> v;
        u--; v--;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    if (m == n) {
        dfs_cycle(0,-1); build_cycle();
        vi cbal;
        for (int r : cycle) {
            dfs(r,-1);
            cbal.pb(bal[r]);
        }

        if (si(cycle) % 2) {
            ll total = 0;
            forn(i,si(cbal)) {
                if (i%2 == 0) total -= cbal[i]; else total += cbal[i];
            }
            if (total%2) result(-1);
            total /= 2;
            for (auto b : cbal) {
                res += abs(total);
                total = -total-b;
            }
            result(res);
        }
        else {
            vector<ll> cum;
            cum.pb(0);
            forn(i,si(cbal)) {
                if (i%2 == 0) cum.pb(cum.back()-cbal[i]);
                else cum.pb(cum.back()+cbal[i]);
            }
            if (cum.back() != 0) result(-1);

            cum.pop_back(); sort(all(cum));
            ll med = cum[si(cum)/2];
            for (ll x : cum) res += abs(x-med);
            result(res);
        }
    }
    else {
        dfs(0,-1);
        if (bal[0] != 0) result(-1);
        result(res);
    }

    return 0;
}

Submission Info

Judge Result