#include "islands.h" #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using pi = pair<int, int>; int n, m; vector<vi> adj, radj; vi istate; struct DSU { int n; vector<int> par; DSU(int N = 0) : n(N), par(N) {iota(par.begin(), par.end(), 0);} int find(int v) {return par[v] == v ? v : par[v] = find(par[v]);} void unite(int a, int b) {if (find(b) != find(a)) par[find(b)] = find(a);} }; variant<bool, vi> find_journey(int N, int M, vi U, vi V) { n = N; m = M; istate.assign(n, 0); adj.resize(n); radj.resize(n); map<pi, int> ec; vi deg(n), indeg(n); for (int i = 0; i < m; i++) { ec[{U[i], V[i]}]++; deg[U[i]]++; indeg[V[i]]++; adj[U[i]].push_back(i); radj[V[i]].push_back(i); } set<pi> r; for (int i = 0; i < n; i++) r.insert({deg[i], i}); while (!r.empty()) { auto cur = *r.begin(); if (cur.first > 0) break; r.erase(cur); for (auto e : radj[cur.second]) { int u = U[e]; if (deg[u] <= 0) continue; r.erase({deg[u], u}); deg[u]--; r.insert({deg[u], u}); } } set<int> vis; vis.insert(0); vi par(n, -1), dist(n, 0); int fx = -1, gx = -1, ex = -1; auto dfs = [&](auto &&self, int u) { if (deg[u] <= 0) return false; for (auto e : adj[u]) { if (deg[V[e]] <= 0) continue; if (vis.count(V[e])) { fx = V[e], gx = u, ex = e; return true; } vis.insert(V[e]); par[V[e]] = e; dist[V[e]] = dist[u] + 1; if (self(self, V[e])) { return true; } } if (fx != -1) { return true; } return false; }; dfs(dfs, 0); if (fx == -1) return false; cout << fx << " " << gx << " " << ex << "\n"; vector<int> j1, j2; while (dist[gx] > dist[fx]) { j1.push_back(par[gx]); gx = U[par[gx]]; } j2.push_back(ex); while (dist[fx] > dist[gx]) { j2.push_back(par[fx]); fx = U[par[fx]]; } // while () reverse(j1.begin(), j1.end()); for (auto &el : j1) cout << el << " "; cout << "\n"; for (auto &el : j2) cout << el << " "; cout << "\n"; vector<int> pre; while (par[fx] != -1) pre.push_back(par[fx]), fx = U[par[fx]]; vector<int> post = pre; reverse(pre.begin(), pre.end()); vector<int> cycle = j1; for (auto &el : j2) cycle.push_back(el); for (int i = 0; i < cycle.size(); i++) pre.push_back((cycle[i]/2)*2); for (int i = 0; i < cycle.size(); i++) pre.push_back(1+(cycle[i]/2)*2); for (int i = cycle.size()-1; i >= 0; i--) pre.push_back((cycle[i]/2)*2); for (int i = cycle.size()-1; i >= 0; i--) pre.push_back(1+(cycle[i]/2)*2); for (auto &el : post) pre.push_back(el); return pre; // return r.size() > 0; // int x = 0, p = -1; // vector<int> pre, maneuver; // set<int> vis; vis.insert(0); // if (deg[0] < 2) { // pre.push_back(adj[0][0]); // x = V[adj[0][0]]; p = 0; // while (deg[x] < 3) { // vis.insert(x); // int y = -1; for (auto e : adj[x]) if (!vis.count(V[e])) {y = e; break;} // if (y == -1) return false; // pre.push_back(y); // x = V[y]; // } // } // if (deg[x] <= (x == 0 ? 1 : 2)) return false; // int a = -1, b = -1, c = -1, d = -1; // for (auto e : adj[x]) { // if (vis.count(V[e])) continue; // if (a == -1) a = e; // else if (c == -1) c = e; // } // if (a%2 == 0) b = a+1; // else b = a-1; // if (c%2 == 0) d = c+1; // else d = c-1; // cout << x << "\n"; // cout << a << " " << b << " " << c << " " << d << "\n"; // if (a < 0 || b < 0 || c < 0 || d < 0) return false; // maneuver.assign({a,b,c,d,b,a,d,c}); // vector<int> post = pre; reverse(post.begin(), post.end()); // for (auto &el : maneuver) pre.push_back(el); // for (auto &el : post) pre.push_back(el); // return pre; }