#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}); } } queue<int> q; q.push(0); set<int> vis; vis.insert(0); while (!q.empty()) { int u = q.front(); q.pop(); if (deg[u] <= 0) continue; for (auto e : adj[u]) { if (deg[V[e]] <= 0) continue; if (vis.count(V[e])) { cout << u << " " << V[e] << "\n"; return true; } vis.insert(V[e]); q.push(V[e]); } } return false; // 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; }