| 17 | } |
| 18 | } |
| 19 | int solve(int n, vector<pair<int, int>> &edges) { |
| 20 | int a; |
| 21 | vector<int> X(n + 1, 0); |
| 22 | int ans = 0; |
| 23 | auto update = [&](int u) { |
| 24 | for (X[u] = 1; C[u][X[u]]; X[u]++); |
| 25 | }; |
| 26 | auto color = [&](int u, int v, int c) { |
| 27 | int p = col[u][v]; |
| 28 | col[u][v] = col[v][u] = c; |
| 29 | ans = max(ans, c); |
| 30 | C[u][c] = v; |
| 31 | C[v][c] = u; |
| 32 | C[u][p] = C[v][p] = 0; |
| 33 | if (p) X[u] = X[v] = p; |
| 34 | else update(u), update(v); |
| 35 | return p; |
| 36 | }; |
| 37 | auto flip = [&](int u, int c1, int c2) { |
| 38 | int p = C[u][c1]; |
| 39 | swap(C[u][c1], C[u][c2]); |
| 40 | if (p) col[u][p] = col[p][u] = c2; |
| 41 | if (!C[u][c1]) X[u] = c1; |
| 42 | if (!C[u][c2]) X[u] = c2; |
| 43 | return p; |
| 44 | }; |
| 45 | for (int i = 1; i <= n; i++) X[i] = 1; |
| 46 | for (int t = 0; t < edges.size(); t++) { |
| 47 | int u = edges[t].first, v0 = edges[t].second, v = v0, c0 = X[u], c = c0, d; |
| 48 | vector<pair<int, int>> L; |
| 49 | vector<int> vis(n + 1, 0); |
| 50 | while (!col[u][v0]) { |
| 51 | L.emplace_back(v, d = X[v]); |
| 52 | if (!C[v][c]) for (a = (int)L.size() - 1; a >= 0; a--) c = color(u, L[a].first, c); |
| 53 | else if (!C[u][d]) for (a = (int)L.size() - 1; a >= 0; a--) color(u, L[a].first, L[a].second); |
| 54 | else if (vis[d]) break; |
| 55 | else vis[d] = 1, v = C[u][d]; |
| 56 | } |
| 57 | if (!col[u][v0]) { |
| 58 | for (; v; v = flip(v, c, d), swap(c, d)); |
| 59 | if (C[u][c0]) { |
| 60 | for (a = (int)L.size() - 2; a >= 0 && L[a].second != c; a--); |
| 61 | for (; a >= 0; a--) color(u, L[a].first, L[a].second); |
| 62 | } else t--; |
| 63 | } |
| 64 | } |
| 65 | return ans; |
| 66 | } |
| 67 | } |
| 68 | int u[N], v[N]; |
| 69 | int32_t main() { |