hashipon.cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define printV(v) for(auto&& x : v){cerr << x << " ";} cerr << endl
#define printVV(vv) for(auto&& v : vv){for(auto&& x : v){cerr << x << " ";}cerr << endl;}
#define printP(p) cerr << p.first << " " << p.second << endl
#define printVP(vp) for(auto&& p : vp) printP(p);

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
const int inf = 1e9;
const int mod = 1e9 + 7;

typedef vector<vector<int>> Graph;
typedef pair<int, int>      Edge;   // (a < b: 無向辺)

class BICC {
private:
    const int n;

    /*** 橋の列挙 ***/
    Graph G;
    vi depth;
    vi par;
    map<Edge, int> imosEdge;
    map<Edge, int> EdgeType;
    enum {UNUSED, USED_DFS, BRIDGE};

    /*** 二重辺連結成分 ***/
	vi cmp;                // cmp[i] = 頂点 i がどの二重辺連結成分に属するか
	int num_cc;            // 二重辺連結成分の個数
	vi size_of_vertex;     // 各二重辺連結成分に含まれる頂点の個数
	Graph G_cc;            // 各二重辺連結成分を頂点とする無向グラフ (!!!木になる!!!)

    /*** この問題用 ***/
    vi leaf_of_subtree;     // iの部分木に含まれる葉の個数
    vi size_of_subtree;     // iの部分木に含まれる頂点のsize_of_vertexの総和
public:
    BICC(int _n) : n(_n), G(_n), depth(_n, -1), par(_n, -1), cmp(_n, -1), num_cc(0) {}
    Edge getEdge(int a, int b) {
        if (a > b) swap(a, b);
        return Edge(a, b);
    }
    void updateEdgeType(int a, int b, int type) {
        if (a < 0 || b < 0) return;			// dfsで-1が与えられるとき用
        EdgeType[getEdge(a, b)] = type;
    }
    void addEdge(int a, int b) {
        G[a].emplace_back(b);
        G[b].emplace_back(a);
        updateEdgeType(a, b, UNUSED);
    }
    void dfsTreeConstruct(int v, int pre) {
        if (depth[v] != -1) return;
        depth[v] = (pre == -1 ? 0 : depth[pre] + 1);
        par[v] = pre;
        updateEdgeType(pre, v, USED_DFS);
        for (auto&& nxt : G[v]) {
            if (nxt != pre) dfsTreeConstruct(nxt, v);
        }
    }
    void updateImos(int a, int b) {
        if (depth[a] < depth[b]) swap(a, b);
        
        // depth[a] > depth[b]: DFSで使われなかった a->b の辺
        if (par[a] != -1) {
            imosEdge[getEdge(a, par[a])]++;
        }
        if (par[b] != -1) {
            imosEdge[getEdge(b, par[b])]--;
        }
    }
    int imosFinal(int v, int pre) {
        int t = 0;
        for (auto&& nxt : G[v]) {
            if (nxt != pre && EdgeType[getEdge(nxt, v)] == USED_DFS) {
                t += imosFinal(nxt, v);
            }
        }
        if (pre != -1) imosEdge[getEdge(v, pre)] += t;
        return pre == -1 ? 0 : imosEdge[getEdge(v, pre)];
    }
    // 1つの連結成分を取り出し、その連結成分の大きさを返す
    int extractCC(int v, int color) {
    	if (cmp[v] != -1) return 0;
    	cmp[v] = color;
    	int t = 1;
    	for (auto&& nxt : G[v]) {
    		if (EdgeType[getEdge(v, nxt)] != BRIDGE) {
    			t += extractCC(nxt, color);
    		}
    	}
    	return t;
    }

    int dfsLeafSubtree(int v, int pre) {
        int ret = (G_cc[v].size() == 1);
        for (auto&& nxt : G_cc[v]) {
            if (nxt != pre) {
                ret += dfsLeafSubtree(nxt, v);
            }
        }
        return leaf_of_subtree[v] = ret;
    }
    int dfsSizeSubtree(int v, int pre) {
        int ret = size_of_vertex[v];
        for (auto&& nxt : G_cc[v]) {
            if (nxt != pre) {
                ret += dfsSizeSubtree(nxt, v);
            }
        }
        return size_of_subtree[v] = ret;
    }
    void bicc() {
        /***	橋の列挙	***/
        vector<Edge> bridges;
        dfsTreeConstruct(0, -1);
        for (auto&& p : EdgeType) {
            Edge e;
            int type;
            tie(e, type) = p;
            if (type == UNUSED) {
                updateImos(e.first, e.second);
            }
        }
        imosFinal(0, -1);
        for (auto&& p : EdgeType) {
            Edge e;
            int type;
            tie(e, type) = p;
            if (type == USED_DFS) {
                if (imosEdge[e] == 0) {
                    EdgeType[e] = BRIDGE;
                    bridges.emplace_back(e);
                }
            }
        }

        /***	二重辺連結成分	***/
		rep(i, n) {
			int size_cc = extractCC(i, num_cc);
			if (size_cc > 0) {
				size_of_vertex.emplace_back(size_cc);
				num_cc++;
			}
		}

		// cerr << "num_cc = " << num_cc << endl;
		// cerr << "cmp: "; printV(cmp);
		// cerr << "size_of_vertex: "; printV(size_of_vertex);

	 	vector<set<int>> G_cc_st(num_cc);	// 頂点の重複を除くためまずsetでつくる
		for (auto&& p : EdgeType) {
            Edge e;
            int type;
            tie(e, type) = p;
            if (type == BRIDGE) {
                // cerr << e.first << " " << e.second << " " << imosEdge[e] << endl;
				G_cc_st[cmp[e.first]].insert(cmp[e.second]);
				G_cc_st[cmp[e.second]].insert(cmp[e.first]);
            }
        }

		rep(i, num_cc) {
			G_cc.emplace_back(vector<int>(all(G_cc_st[i])));
		}

		// cerr << "---BICC---" << endl;
		// rep(i, num_cc) {
		// 	cerr << i << ": "; printV(G_cc[i]);
		// }

        /***    この問題用   ***/
        leaf_of_subtree.resize(num_cc);
        dfsLeafSubtree(0, -1);
        size_of_subtree.resize(num_cc);
        dfsSizeSubtree(0, -1);

        // cerr << "leaf_of_subtree: "; printV(leaf_of_subtree);
        // cerr << "size_of_subtree: "; printV(size_of_subtree);

    }

    // 辺 = {a, b} をただ1つの橋にするために追加する必要のある辺の本数を返す
    int solve(int i, int j) {
        if (size_of_subtree[i] > size_of_subtree[j]) {
            swap(i, j);
        }

        // size_of_subtree[i] < size_of_subtree[j]
        // すなわち、iの方がjより親から遠い
        int ret = 0;
        if (size_of_subtree[i] == 2) {
            // 閉路ができるのでダメ
            return inf;
        }
        if (G_cc[i].size() > 1) {
            // i の部分木の葉の個数(iの次数が2だったら葉が1つ増える)
            int leaf_i = leaf_of_subtree[i] + (G_cc[i].size() == 2) ;
            ret += (leaf_i + 1) / 2;
        }

        int size_j = n - size_of_subtree[i];
        if (size_j == 2) {
            return inf;
        }
        if (G_cc[j].size() > 1) {
            int leaf_j = leaf_of_subtree[0] - leaf_of_subtree[i] + (G_cc[j].size() == 2);
            ret += (leaf_j + 1) / 2;
        }

        return ret;
    }

    void answer() {
        bicc();
        int ans = inf;
        rep(i, num_cc) {
            for (auto&& j : G_cc[i]) {
                ans = min(ans, solve(i, j));
            }
        }

        if (ans == inf) {
            cout << "IMPOSSIBLE" << endl;
        } else {
            cout << ans << endl;
        }
    }
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int V, E;
    cin >> V >> E;
    BICC bicc(V);
    rep(i, E) {
        int a, b;
        cin >> a >> b;
        bicc.addEdge(a, b);
    }

    bicc.answer();
}