#include<bits/stdc++.h> #include "islands.h" #define fi first #define se second using namespace std; const int MAXN=1e5+5; queue Q; vector <pair<int,int>> in[MAXN]; set <pair<int,int>> G[MAXN]; void topo() { while(Q.size()) { int u=Q.front(); Q.pop(); for(auto e:in[u]) if(G[e.fi].size()) { G[e.fi].erase({u,e.se}); if(G[e.fi].empty()) Q.push(e.fi); } } } vector ans; bool c[MAXN2]; int ct=0,s=0; void dfs(int u,int fz) { if(u==s&&!ct&&~fz) return ; for(auto e:G[u]) if(e.se^fz) { ans.push_back(e.se),c[e.se]^=1,ct+=2c[e.se]-1; G[e.fi].insert({u,e.se}),G[u].erase(e); dfs(e.fi,e.se); return ; } } variant<bool,vector> find_journey(int n,int m,vectorU,vectorV) { for(int i=0;i<m;++i) G[U[i]].insert({V[i],i}),in[V[i]].push_back({U[i],i}); for(int i=0;i<n;++i) if(G[i].empty()) Q.push(i); topo(); while(G[s].size()<2) { if(G[s].empty()) return false; int t=G[s].begin()->fi; ans.push_back(G[s].begin()->se); G[s].clear(),Q.push(s),s=t,topo(); } int o=ans.size(); for(int i=0;i<n;++i) while(G[i].size()>1+(i==s)) G[i].erase(G[i].begin()); dfs(s,-1); for(int i=o-1;~i;--i) ans.push_back(ans[i]); return ans; }