#include "islands.h"
#include <variant>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
// global
int n, m;
const int mxN = 1e5 + 1;
vector<int> adj[mxN], opp[mxN];
bool vis[mxN];
void resetvis() {
for (int i = 0; i < n; i++) vis[i] = false;
}
map<pii, vector<int> > mp, newmp;
int par[mxN];
int vispos[mxN];
vector<int> path;
int loopstart = -1;
void dupcycledfs(int u = 0, int pp = -1) {
vis[u] = true;
par[u] = pp;
vispos[u] = path.size();
path.pb(u);
for (int v : adj[u]) {
if (!vis[v]) {
dupcycledfs(v, u);
} else {
int child = path[vispos[v] + 1];
if (mp[{v, child}].size() >= 2) {
loopstart = v;
return;
}
}
}
path.pop_back();
vispos[u] = -1;
}
vector<int> order;
void SCCDFS1(int u = 0) {
vis[u] = true;
for (int v : adj[u]) {
if (!vis[v]) SCCDFS1(v);
}
order.pb(u);
}
int rep[mxN];
bool iscycle[mxN];
void SCCDFS2(int u, int tar) {
vis[u] = true;
rep[u] = tar;
for (int v : opp[u]) {
if (!vis[v]) {
SCCDFS2(v, tar);
iscycle[tar] = true;
}
}
}
vector<pair<int, bool> > newadj[mxN];
int come[mxN];
int cycleno = -1;
void dfs1(int u = 0, bool dupedge = false) {
if (cycleno != -1) return;
vis[u] = true;
for (pair<int, bool> v : newadj[u]) {
come[v.ff] += (!dupedge ? 1 : 2);
if (come[v.ff] >= 2 && iscycle[v.ff]) {
cycleno = v.ff;
return;
}
if (!vis[v.ff]) {
dfs1(v.ff, dupedge | v.ss);
}
}
}
vector<int> gencyclenode, gencycle;
bool gencycledfsdone = false;
void dfsgencycle(int u) {
if (gencycledfsdone) return;
vis[u] = true;
gencyclenode.pb(u);
for (int v : adj[u]) {
if (!vis[v]) {
dfsgencycle(v);
} else if (v == rep[u]) {
gencycledfsdone = true;
return;
}
}
}
bool prevpathdone = false;
vector<int> godownpath[2];
void dfsfindpath(int u, bool dupedge) {
vis[u] = true;
for (pair<int, bool> v : newadj[u]) {
}
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
n = N; m = M;
for (int i = 0; i < m; i++) {
mp[{U[i], V[i]}].pb(i);
if (mp[{U[i], V[i]}].size() > 2) mp[{U[i], V[i]}].pop_back();
}
for (pair<pii, vector<int> > cur : mp) {
adj[cur.ff.ff].pb(cur.ff.ss);
opp[cur.ff.ss].pb(cur.ff.ff);
}
// check 2 edges in loop case
dupcycledfs();
resetvis();
if (loopstart != -1) {
vector<int> ans;
int looppos = vispos[loopstart];
for (int i = 0; i < int(path.size()) + 1; i++) {
ans.pb(mp[{path[i], path[i + 1]}][0]);
}
ans.pb(mp[{path[looppos], path[looppos + 1]}][1]);
ans.pb(mp[{path[looppos], path[looppos + 1]}][0]);
for (int i = int(path.size()) - 2; i > looppos; i--) {
ans.pb(mp[{path[i], path[i + 1]}][0]);
}
ans.pb(mp[{path[looppos], path[looppos + 1]}][1]);
for (int i = looppos - 1; i >= 0; i--) {
ans.pb(mp[{path[i], path[i + 1]}][0]);
}
return ans;
}
//
SCCDFS1();
reverse(order.begin(), order.end());
resetvis();
rep[0] = 0; vis[0] = true;
for (int &u : order) {
if (!vis[u]) {
SCCDFS2(u, u);
}
}
resetvis();
for (int i = 0; i < m; i++) {
if (!vis[U[i]] || !vis[V[i]]) continue;
int nu = rep[U[i]], nv = rep[V[i]];
if (nu == nv) continue;
newmp[{nu, nv}].pb(i);
if (newmp[{nu, nv}].size() > 2) newmp[{nu, nv}].pop_back();
}
for (pair<pii, vector<int> > cur : newmp) {
newadj[cur.ff.ff].pb({cur.ff.ss, (cur.ss.size() == 2)});
}
dfs1();
resetvis();
if (cycleno == -1) return false;
return true;
for (int i = 0; i < n; i++) {
vis[i] = (rep[i] != cycleno);
}
dfsgencycle(cycleno);
for (int i = 1; i < int(gencyclenode.size()); i++) {
gencycle.pb(mp[{gencyclenode[i - 1], gencyclenode[i]}][0]);
}
gencycle.pb(mp[{gencyclenode.back(), gencyclenode.front()}][0]);
}
