#include "islands.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)
vb remove_zero_or_one_outdeg(int n, int m, const vvpi& adj, const vvpi& adjt) {
vb removed(n, false);
vi outdeg(n, 0);
vi indeg(n, 0);
queue<int> q;
for(int i = 0; i < n; i++) {
outdeg[i] = adj[i].size();
indeg[i] = adjt[i].size();
if(outdeg[i] == 0) q.push(i);
}
while(!q.empty()) {
int i = q.front();
q.pop();
if(removed[i]) continue;
removed[i] = true;
for(auto [j, _] : adjt[i]) {
outdeg[j]--;
if(outdeg[j] == 0) q.push(j);
}
}
return removed;
}
pair<vi, int> find_starting_node(int n, int m, const vvpi& adj) {
vb vis(n, false);
int cur = 0;
vi path;
if(adj[cur].size() > 1) return {path, 0};
vis[cur] = true;
while(adj[cur].size() <= 1) {
// if(adj[cur].size() == 0) return {path, -1};
path.pb(adj[cur][0].se);
cur = adj[cur][0].fi;
if(vis[cur]) return {path, -1};
vis[cur] = true;
}
return {path, cur};
}
// returns gng^-1
vi conjugate(const vi& g, const vi& n) {
int gs = g.size(), ns = n.size();
vi res;
for(int i = 0; i < gs; i++) {
res.pb(g[i]);
}
for(int i = 0; i < ns; i++) {
res.pb(n[i]);
}
for(int i = gs - 1; i >= 0; i--) {
res.pb(g[i]);
}
return res;
}
vi invert_path(const vi& path) {
vi res;
for(int i = path.size() - 1; i >= 0; i--) {
res.pb(path[i]);
}
return res;
}
vi chain_paths(const vi& p1, const vi& p2) {
vi res = p1;
int p2s = p2.size();
for(int i = 0; i < p2s; i++) {
res.pb(p2[i]);
}
return res;
}
pair<vi, vi> find_cycle(int s, int n, int start_edge_ind, const vvpi& adj) {
vb vis(n, false);
int cur = s;
// vis[cur] = true;
// cur = adj[cur][start_edge_ind].fi;
while(!vis[adj[cur][0].fi]) {
vis[cur] = true;
cur = adj[cur][0].fi;
}
int loop_n = adj[cur][0].fi;
vi tail;
vi cyc;
cur = s;
if(cur != loop_n) {
// tail.pb(adj[cur][start_edge_ind].se);
// cur = adj[cur][start_edge_ind].fi;
while(cur != loop_n) {
tail.pb(adj[cur][0].se);
cur = adj[cur][0].fi;
}
}
do {
cyc.pb(adj[cur][0].se);
cur = adj[cur][0].fi;
} while(cur != loop_n);
return {tail, cyc};
}
// vi shift_cycle(const vi& cyc, int sn, const vi& v) {
// int cycs = cyc.size();
// int start_ind = -1;
// for(int i = 0; i < cycs; i++) {
// if(v[cyc[i]] == sn) {
// start_ind = i;
// break;
// }
// }
// start_ind++;
// start_ind %= cycs;
// vi res(cycs, 0);
// for(int i = 0; i < cycs; i++) {
// res[i] = cyc[(i + start_ind) % cycs];
// }
// return res;
// }
bool is_distinct(const vi& l1, const vi& l2) {
int l1s = l1.size(), l2s = l2.size();
int l1p = 0, l2p = 0;
while(l1p < l1s && l2p < l2s) {
if(l1[l1p] < l2[l2p]) l1p++;
else if(l1[l1p] > l2[l2p]) l2p++;
else return false;
}
return true;
}
bool is_reachable(const vi& path, vi u, vi v) {
int ps = path.size();
for(int i = 0; i < ps - 1; i++) {
int temp = u[path[i]];
u[path[i]] = v[path[i]];
v[path[i]] = temp;
if(u[path[i]] != u[path[i + 1]]) return false;
}
return true;
}
variant<bool, vi> find_journey(int n, int m, vi u, vi v) {
vvpi adj;
vvpi adjt;
for(int i = 0; i < n; i++) {
vpi adjr;
vpi adjtr;
adj.pb(adjr);
adjt.pb(adjtr);
}
for(int i = 0; i < m; i++) {
adj[u[i]].pb({v[i], i});
adjt[v[i]].pb({u[i], i});
}
// Remove zero outdeg
vb to_remove = remove_zero_or_one_outdeg(n, m, adj, adjt);
if(to_remove[0]) {
return false; // If island 0 is removed, it's impossible
}
// Update adj
for(int i = 0; i < n; i++) {
adj[i].clear();
adjt[i].clear();
}
for(int i = 0; i < m; i++) {
if(to_remove[u[i]] || to_remove[v[i]]) continue;
adj[u[i]].pb({v[i], i});
adjt[v[i]].pb({u[i], i});
}
// Start from 0, find a node with outdegree >= 2. Call it X
// Start from X, use canoe 1 and proceed until you cycle. Take note of the nodes in the cycle
// Start from X, use canoe 2 and proceed until you cycle. Take note of the nodes in the cycle
// If you can't find such a node, conclude that it is impossible
auto [g, x] = find_starting_node(n, m, adj);
if(x == -1) {
return false;
}
// CASE 1: If the cycle EDGES intersect at any point, replace one of the cycles with the other.
// It doesn't matter which, just use the same cycle
// g n1 cycle n1inv n2 cycleinv n2inv ginv
// CASE 2: the cycles are EDGE-disjoint
// g n1 cycle1 n1inv n2 cycle2 n2inv n1 cycle1inv n1inv n2 cycle2inv n2inv ginv
int n1_scanoe = adj[x][0].se, n2_scanoe = adj[x][1].se;
int n1_sn = adj[x][0].fi, n2_sn = adj[x][1].fi;
auto [n1tail, n1cyc] = find_cycle(x, n, 0, adj);
auto [n2tail, n2cyc] = find_cycle(n2_sn, n, 0, adj);
// int n1_scycn = (n1tail.size() == 0 ? n1_sn : v[n1tail.back()]);
// int n2_scycn = (n2tail.size() == 0 ? n2_sn : v[n2tail.back()]);
reverse(n2tail.begin(), n2tail.end());
n2tail.pb(n2_scanoe);
reverse(n2tail.begin(), n2tail.end());
vi n1cycs = n1cyc, n2cycs = n2cyc;
sort(n1cycs.begin(), n1cycs.end());
sort(n2cycs.begin(), n2cycs.end());
// for(int& v : n1tail) cout << v << " ";
// cout << "\n";
// for(int& v : n1cyc) cout << v << " ";
// cout << "\n";
// for(int& v : n2tail) cout << v << " ";
// cout << "\n";
// for(int& v : n2cyc) cout << v << " ";
// cout << "\n";
// check if distinct
vi ans;
if(is_distinct(n1cycs, n2cycs)) {
// The cycles are edge-disjoint, case 2
// g n1 cycle1 n1inv n2 cycle2 n2inv n1 cycle1inv n1inv n2 cycle2inv n2inv ginv
vi cyc_forward = chain_paths(conjugate(n1tail, n1cyc), conjugate(n2tail, n2cyc));
vi cyc_backward = chain_paths(conjugate(n1tail, invert_path(n1cyc)), conjugate(n2tail, invert_path(n2cyc)));
ans = conjugate(g, chain_paths(cyc_forward, cyc_backward));
} else {
// The cycles are NOT edge-disjoint, case 1
// g n1 cycle n1inv n2 cycleinv n2inv ginv
ans = conjugate(g, chain_paths(conjugate(n1tail, n1cyc), conjugate(n2tail, invert_path(n2cyc))));
}
// ! NOTE: it may help to have a utility function for "shifting" a cycle to start at some arbitrary node
// It may also help to have a utility "reverse" function.
// This is rather simple actually, just get a list of canoes and reverse it
// It might not be necessary
bool has_rep = false;
int ans_sz = ans.size();
for(int i = 0; i < ans_sz - 1; i++) {
if(ans[i] == ans[i + 1]) {
has_rep = true;
break;
}
}
if(has_rep) return false;
if(!is_reachable(ans, u, v)) return false;
return ans;
}
