#include #include #define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++) using namespace std; using namespace atcoder; typedef long long ll; struct edge { int to; int label; }; vector> gabow_edmonds(const vector>& gra) { // E0 - 初期化 int N = gra.size(); ::std::vector<::std::vector> g(N + 1); ::std::vector<::std::pair> edges; { int cnt = N + 1; for (int i = 0; i < N; i++) { for (auto to : gra[i]) { if (i < to) { g[to + 1].push_back({i + 1, cnt}); g[i + 1].push_back({to + 1, cnt++}); edges.push_back({i + 1, to + 1}); } } } } ::std::vector mate(N + 1, 0); ::std::vector label(N + 1, -1); ::std::vector first(N + 1, 0); ::std::queue que; // firstの遅延評価 ::std::function eval_first = [&](int x) { if (label[first[x]] < 0) return first[x]; first[x] = eval_first(first[x]); return first[x]; }; // サブルーチンR ::std::function rematch = [&](int v, int w) { // R1 int t = mate[v]; mate[v] = w; if (mate[t] != v) return; // R2 if (label[v] <= N) { mate[t] = label[v]; rematch(label[v], t); } // R3 else { int x = edges[label[v] - N - 1].first; int y = edges[label[v] - N - 1].second; rematch(x, y); rematch(y, x); } }; ::std::function assignLabel = [&](int x, int y, int num) { // L0 int r = eval_first(x); int s = eval_first(y); int join = 0; if (r == s) return; // -numがフラグ label[r] = -num; label[s] = -num; while (true) { // L1 if (s != 0) ::std::swap(r, s); // L2 r = eval_first(label[mate[r]]); if (label[r] == -num) { join = r; break; } label[r] = -num; } // L3 int v = first[x]; // L4 while (v != join) { que.push(v); label[v] = num; first[v] = join; v = first[label[mate[v]]]; } // L3 v = first[y]; // L4 while (v != join) { que.push(v); label[v] = num; first[v] = join; v = first[label[mate[v]]]; } // L5は遅延評価しているため不要 // L6 return; }; ::std::function augment_check = [&](int u) { // E1 後半 first[u] = 0; label[u] = 0; que.push(u); while (!que.empty()) { // E2 int x = que.front(); que.pop(); for (auto e : g[x]) { int y = e.to; // E3 if (mate[y] == 0 && y != u) { mate[y] = x; rematch(x, y); return true; } // E4 else if (label[y] >= 0) { assignLabel(x, y, e.label); } // E5 else if (label[mate[y]] < 0) { label[mate[y]] = x; first[mate[y]] = y; que.push(mate[y]); } // E6 } } return false; }; for (int i = 1; i <= N; i++) { // E1 que = ::std::queue(); if (mate[i] != 0) continue; if (augment_check(i)) { // E7 ::std::fill(label.begin(), label.end(), -1); } } ::std::vector<::std::pair> ans; for (int i = 1; i <= N; i++) { if (i < mate[i]) { ans.push_back({i - 1, mate[i] - 1}); } } return ans; } int main() { int n, m; cin >> n >> m; map, int> mp; vector> gra(n); rep(i, 0, m) { int a, b; cin >> a >> b; a--; b--; gra[a].push_back(b); gra[b].push_back(a); mp[{a, b}] = i; mp[{b, a}] = i; } auto ans = gabow_edmonds(gra); cout << ans.size() << endl; for (auto p : ans) { cout << mp[{p.first, p.second}] + 1 << endl; } }