/*******************
* what the sigma *
********************/
#include <iostream>
#include <vector>
#include <map>
#include <chrono>
#include <set>
#include <queue>
#include <algorithm>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set(x) tree<x, null_type, less<x>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
#define lgm cin.tie(0)->sync_with_stdio(0);
#define be(x) x.begin(),x.end()
#define ve vector
#define ll long long
#define ld long double
bool enabledb=0;
#define DB(CODE) cout<<'\t'<<CODE<<endl;
#define SP <<' '<<
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int, int>
#define tii tuple<int,int,int>
#define pll pair<ll,ll>
#define tll tuple<ll,ll,ll>
#define sz(x) ((int)x.size())
#define pb push_back
const ll mod = 1e9+7,maxn=300005;
const ll INF=(ll)9e18;
struct pDSU{
ve<int> pa;
ve<int> szz;
ve<int> tpa;
ve<int> tdeg3;
ve<int> tcyc;
ve<int> deg;
pDSU(int N):pa(N),szz(N,1),tpa(N),tdeg3(N),deg(N),tcyc(N){
for (int i=0;i<N;i++) {
pa[i]=i;
tpa[i]=-1;
tcyc[i]=-1;
tdeg3[i]=-1;
deg[i]=0;
}
}
int find(int u,int time) {
if (tpa[u]!=-1&&tpa[u]<=time) {
return find(pa[u],time);
}
return u;
}
void unite(int u,int v,int time) {
deg[u]++;
deg[v]++;
bool b=(deg[u]>=3||deg[v]>=3);
int x=find(u,time);
int y=find(v,time);
if (x==y) {
if (tcyc[x]==-1) {
tcyc[x]=time;
}
if (tdeg3[x]==-1&&b) {
tdeg3[x]=time;
}
} else {
if (szz[x]<szz[y]) {
swap(x,y);
}
pa[y]=x;
if (tdeg3[y]!=-1&&tdeg3[x]==-1) {
tdeg3[x]=time;
}
if (tcyc[y]!=-1&&tcyc[x]==-1) {
tcyc[x]=time;
}
szz[x]+=szz[y];
tpa[y]=time;
if (b&&tdeg3[x]==-1) {
tdeg3[x]=time;
}
}
}
int query(int u,int time) {
u=find(u,time);
int ans=tdeg3[u];
if (tcyc[u]!=-1) {
if (ans==-1) {
ans=tcyc[u];
} else {
ans=min(ans,tcyc[u]);
}
}
return ans;
}
};
void init(int N, int M, int U,int V, int W) {
//hi
}
ll getMinimumFuelCapacity(int X,int Y) {
//bye
}
