#include "islands.h"
#include <variant>
#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
const int SZ=1<<17;
vector<pair<int,int>> adj[100000];
vector<int> tadj[100000], radj[100000], S, Q[100000], FQ[100000], CQ[100000], ans;
set<pair<int,int>> FE;
map<pair<int,int>,int> E, SE;
int node_cnt, W[100000], num[100000], hld[100000], R[100000], parent[100000], depth[100000], D[100000];
bool chk[100000];
pair<int,int> tree[2*SZ], lazy[2*SZ];
void solution1(int a, int b, int e);
void solution2(int a, int b, pair<int,int> c);
void solution3(pair<int,int> a, pair<int,int> b);
void solution4(int a, int b);
pair<int,int> get_max(pair<int,int> a, pair<int,int> b)
{
if(a==make_pair(-1,-1)) return b;
if(b==make_pair(-1,-1)) return a;
return depth[a.first]>depth[b.first] ? a:b;
}
void lazy_propagation(int bit, int s, int e)
{
if(lazy[bit]==make_pair(-1,-1)) return;
tree[bit]=get_max(tree[bit],lazy[bit]);
if(s<e) {
lazy[2*bit]=get_max(lazy[2*bit],lazy[bit]);
lazy[2*bit+1]=get_max(lazy[2*bit+1],lazy[bit]);
}
lazy[bit]={-1,-1};
}
void update(int n1, int n2, pair<int,int> v, int bit=1, int s=0, int e=SZ-1)
{
int m=(s+e)>>1;
lazy_propagation(bit,s,e);
if(n2<n1 || n2<s || e<n1) return;
if(n1<=s && e<=n2) {
lazy[bit]=v;
lazy_propagation(bit,s,e);
return;
}
update(n1,n2,v,2*bit,s,m);
update(n1,n2,v,2*bit+1,m+1,e);
tree[bit]=get_max(tree[2*bit],tree[2*bit+1]);
}
pair<int,int> query(int n1, int n2, int bit=1, int s=0, int e=SZ-1)
{
int m=(s+e)>>1;
lazy_propagation(bit,s,e);
if(n2<n1 || n2<s || e<n1) return {-1,-1};
if(n1<=s && e<=n2) return tree[bit];
return get_max(query(n1,n2,2*bit,s,m),query(n1,n2,2*bit+1,m+1,e));
}
void dfs(int c)
{
S.push_back(c);
W[c]=chk[c]=true;
for(auto[n,e]: adj[c]) {
if(E.count({c,n})) SE[{c,n}]=e;
else E[{c,n}]=e;
if(W[n]==0) {
tadj[c].push_back(n);
parent[n]=c;
D[n]=depth[n]=depth[c]+1;
dfs(n);
W[c]+=W[n];
}
else if(chk[n]) Q[S[depth[n]+1]].push_back(c);
else if(FE.find({c,n})!=FE.end()) FQ[c].push_back(n);
else CQ[c].push_back(n);
}
for(auto n: radj[c]) if(chk[n]) FE.emplace(n,c);
chk[c]=false;
S.pop_back();
}
void dfs2(int c)
{
int mx=-1;
num[c]=node_cnt++;
S.push_back(c);
for(auto n: Q[c]) {
if(D[c]==D[parent[c]]) {
solution1(parent[c],n,SE[{parent[c],c}]);
return;
}
if(D[parent[c]]!=depth[parent[c]]) {
solution4(parent[c],n);
return;
}
auto q=query(num[c],num[c]+W[c]-1);
if(q!=make_pair(-1,-1)) {
solution3(q,make_pair(parent[c],n));
return;
}
update(0,num[c]-1,make_pair(parent[c],n));
update(num[c]+W[c],SZ-1,make_pair(parent[c],n));
}
for(auto n: tadj[c]) if(mx==-1 || W[mx]<W[n]) mx=n;
if(mx==-1) {
S.pop_back();
R[c]=node_cnt-1;
return;
}
hld[mx]=hld[c];
if(SE.count({c,mx})) D[mx]=D[c];
dfs2(mx);
if(ans.size()) return;
for(auto n: tadj[c]) if(mx!=n) {
if(SE.count({c,n})) D[n]=D[c];
dfs2(hld[n]=n);
if(ans.size()) return;
}
R[c]=node_cnt-1;
S.pop_back();
}
void query(int a, int b, pair<int,int> v)
{
while(hld[a]!=hld[b]) {
update(num[hld[b]],num[b],v);
b=parent[hld[b]];
}
update(num[a],num[b],v);
}
void dfs3(int c)
{
for(auto n: tadj[c]) if(parent[n]==c) {
dfs3(n);
if(ans.size()) return;
}
for(auto n: Q[c]) query(c,n,make_pair(parent[c],n));
for(auto n: FQ[c]) {
auto q=query(num[n],num[n]);
if(q!=make_pair(-1,-1) && depth[c]<=depth[q.first]) {
solution2(c,n,q);
return;
}
}
for(auto n: CQ[c]) {
auto q=query(num[n],num[n]);
if(q!=make_pair(-1,-1)) {
solution2(c,n,q);
return;
}
}
}
variant<bool,vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V)
{
ans.clear(); S.clear(); E.clear(); SE.clear();
for(int i=0;i<N;i++) {
adj[i].clear(); Q[i].clear(); FQ[i].clear(); CQ[i].clear();
tadj[i].clear(); radj[i].clear();
W[i]=chk[i]=false;
}
for(int i=2*SZ;--i;) tree[i]=lazy[i]={-1,-1};
for(int i=0;i<M;i++) {
adj[U[i]].emplace_back(V[i],i);
radj[V[i]].push_back(U[i]);
}
dfs(0); dfs2(0);
if(ans.empty()) {
for(int i=2*SZ;--i;) tree[i]=lazy[i]={-1,-1};
dfs3(0);
if(ans.size()) return ans;
return false;
}
return ans;
}
void solution1(int a, int b, int e)
{
vector<int> ZA, A, temp;
A.push_back(a); A.push_back(b); ZA.push_back(a);
for(int i=a;i;i=parent[i]) ZA.push_back(parent[i]);
reverse(ZA.begin(),ZA.end());
swap(temp,ZA); ZA.clear();
for(int i=1;i<temp.size();i++) ZA.push_back(E[{temp[i-1],temp[i]}]);
for(int i=b;i!=a;i=parent[i]) A.push_back(parent[i]);
reverse(A.begin(),A.end());
swap(temp,A); A.clear();
for(int i=1;i<temp.size();i++) A.push_back(E[{temp[i-1],temp[i]}]);
for(auto a: ZA) ans.push_back(a);
for(auto a: A) ans.push_back(a);
ans.push_back(e); ans.push_back(A[0]); A[0]=e;
reverse(A.begin(),A.end()); reverse(ZA.begin(),ZA.end());
for(auto a: A) ans.push_back(a);
for(auto a: ZA) ans.push_back(a);
}
void solution2(int a, int b, pair<int,int> c)
{
vector<int> L, LA, LB, A, B, temp;
int l, x=a, y=c.first;
if(depth[x]<depth[y]) swap(x,y);
while(depth[x]!=depth[y]) x=parent[x];
while(x!=y) {
x=parent[x];
y=parent[y];
}
L.push_back(l=x);
for(int i=l;i;i=parent[i]) L.push_back(parent[i]);
reverse(L.begin(),L.end());
swap(temp,L); L.clear();
for(int i=1;i<temp.size();i++) L.push_back(E[{temp[i-1],temp[i]}]);
LA.push_back(x=c.first); LB.push_back(b); LB.push_back(a);
for(int i=x;i!=l;i=parent[i]) LA.push_back(parent[i]);
reverse(LA.begin(),LA.end());
swap(temp,LA); LA.clear();
for(int i=1;i<temp.size();i++) LA.push_back(E[{temp[i-1],temp[i]}]);
for(int i=a;i!=l;i=parent[i]) LB.push_back(parent[i]);
reverse(LB.begin(),LB.end());
swap(temp,LB); LB.clear();
for(int i=1;i<temp.size();i++) LB.push_back(E[{temp[i-1],temp[i]}]);
A.push_back(x); A.push_back(c.second);
for(int i=c.second;i!=x;i=parent[i]) A.push_back(parent[i]);
reverse(A.begin(),A.end());
for(int i=1;i<A.size();i++) if(A[i]==b) {
for(int j=i;j<A.size();j++) B.push_back(A[j]);
for(int j=1;j<=i;j++) B.push_back(A[j]);
break;
}
swap(temp,A); A.clear();
for(int i=1;i<temp.size();i++) A.push_back(E[{temp[i-1],temp[i]}]);
swap(temp,B); B.clear();
for(int i=1;i<temp.size();i++) B.push_back(E[{temp[i-1],temp[i]}]);
for(auto a: L) ans.push_back(a);
for(auto a: LA) ans.push_back(a);
for(auto a: A) ans.push_back(a);
reverse(LA.begin(),LA.end());
for(auto a: LA) ans.push_back(a);
for(auto a: LB) ans.push_back(a);
reverse(B.begin(),B.end());
for(auto a: B) ans.push_back(a);
reverse(LB.begin(),LB.end());
for(auto a: LB) ans.push_back(a);
reverse(L.begin(),L.end());
for(auto a: L) ans.push_back(a);
}
void solution3(pair<int,int> a, pair<int,int> b)
{
vector<int> L, LA, LB, A, B, temp;
int l, x=a.first, y=b.first;
if(depth[x]<depth[y]) swap(x,y);
while(depth[x]!=depth[y]) x=parent[x];
while(x!=y) {
x=parent[x];
y=parent[y];
}
L.push_back(l=x);
for(int i=l;i;i=parent[i]) L.push_back(parent[i]);
reverse(L.begin(),L.end());
swap(temp,L); L.clear();
for(int i=1;i<temp.size();i++) L.push_back(E[{temp[i-1],temp[i]}]);
A.push_back(x=a.first); B.push_back(y=b.first);
A.push_back(a.second); B.push_back(b.second);
LA.push_back(x); LB.push_back(y);
for(int i=x;i!=l;i=parent[i]) LA.push_back(parent[i]);
for(int i=y;i!=l;i=parent[i]) LB.push_back(parent[i]);
reverse(LA.begin(),LA.end()); reverse(LB.begin(),LB.end());
swap(temp,LA); LA.clear();
for(int i=1;i<temp.size();i++) LA.push_back(E[{temp[i-1],temp[i]}]);
swap(temp,LB); LB.clear();
for(int i=1;i<temp.size();i++) LB.push_back(E[{temp[i-1],temp[i]}]);
for(int i=a.second;i!=x;i=parent[i]) A.push_back(parent[i]);
for(int i=b.second;i!=y;i=parent[i]) B.push_back(parent[i]);
reverse(A.begin(),A.end()); reverse(B.begin(),B.end());
swap(temp,A); A.clear();
for(int i=1;i<temp.size();i++) A.push_back(E[{temp[i-1],temp[i]}]);
swap(temp,B); B.clear();
for(int i=1;i<temp.size();i++) B.push_back(E[{temp[i-1],temp[i]}]);
for(auto a: L) ans.push_back(a);
for(auto a: LA) ans.push_back(a);
for(auto a: A) ans.push_back(a);
reverse(LA.begin(),LA.end());
for(auto a: LA) ans.push_back(a);
for(auto a: LB) ans.push_back(a);
for(auto a: B) ans.push_back(a);
reverse(LB.begin(),LB.end());
for(auto a: LB) ans.push_back(a);
reverse(LA.begin(),LA.end());
for(auto a: LA) ans.push_back(a);
reverse(A.begin(),A.end());
for(auto a: A) ans.push_back(a);
reverse(LA.begin(),LA.end());
for(auto a: LA) ans.push_back(a);
reverse(LB.begin(),LB.end());
for(auto a: LB) ans.push_back(a);
reverse(B.begin(),B.end());
for(auto a: B) ans.push_back(a);
reverse(LB.begin(),LB.end());
for(auto a: LB) ans.push_back(a);
reverse(L.begin(),L.end());
for(auto a: L) ans.push_back(a);
}
void solution4(int a, int b)
{
vector<int> ZA, A, temp;
A.push_back(a); A.push_back(b); ZA.push_back(a);
for(int i=a;i;i=parent[i]) ZA.push_back(parent[i]);
reverse(ZA.begin(),ZA.end());
swap(temp,ZA); ZA.clear();
for(int i=1;i<temp.size();i++) ZA.push_back(E[{temp[i-1],temp[i]}]);
for(int i=b;i!=a;i=parent[i]) A.push_back(parent[i]);
reverse(A.begin(),A.end());
swap(temp,A); A.clear();
for(int i=1;i<temp.size();i++) A.push_back(E[{temp[i-1],temp[i]}]);
for(auto a: ZA) ans.push_back(a);
for(auto a: A) ans.push_back(a);
ans.push_back(ZA.back()); ans.push_back(ZA.back()=SE[{parent[a],a}]);
reverse(A.begin(),A.end()); reverse(ZA.begin(),ZA.end());
for(auto a: A) ans.push_back(a);
for(auto a: ZA) ans.push_back(a);
}
