#include<bits/stdc++.h>
#include "swap.h"
//#include "grader.cpp"
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int>vi;
typedef vector<vector<int>>vvi;
typedef vector<ll>vl;
typedef vector<vl> vvl;
typedef pair<int,int>pi;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld,ld> pld;
//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T> ostream& operator<<(ostream& os, vector<T>& a){os<<"[";for(int i=0; i<ll(a.size()); i++){os << a[i] << ((i!=ll(a.size()-1)?" ":""));}os << "]\n"; return os;}
#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map
struct dsu{
vi par,deg;
vector<bool>is_line;
dsu (int n){
par.resize(n);
for(int i=0; i<n; i++)
par[i]=i;
deg.resize(n);
is_line.resize(n,1);
}
int get(int x){return par[x]=(x==par[x]?x:get(par[x]));}
void unite(int u,int v){
bool ok=(deg[u]+1)>2 || (deg[v]+1)>2 || get(u)==get(v);
deg[u]++,deg[v]++;
if(rand()%2)swap(u,v);
if(ok)
is_line[get(u)]=is_line[get(v)]=0;
if(!is_line[get(u)] || !is_line[get(v)])
is_line[get(u)]=is_line[get(v)]=0;
u=get(u),v=get(v);
par[u]=v;
}
};
vector<vector<pi>> g;
vector<bool>vis;
int mx=-1;
bool cyc=1,line=1,star=1;
vvi E;
void init(int n, int M,vi U,vi V,vi W){
g.resize(n);
vis.resize(n);
mx=*max_element(all(W))+1;
for(int i=0; i<M; i++){
g[U[i]].pb({V[i],W[i]});
g[V[i]].pb({U[i],W[i]});
E.pb({W[i],min(U[i],V[i]),max(U[i],V[i])});
}
sort(all(E));
for(int i=0; i<n; i++)
cyc&=g[i].size()==2,line&=g[i].size()<=2;
line&=!cyc;
star&=g[0].size()==n-1 && M==n-1;
}
bool ans;
void dfs(int src,int par,int w){
vis[src]=1;
int cnt=0;
for(pi nbr:g[src])
if(nbr.second<=w)
cnt++;
if(cnt>2)
ans=1;
for(pi nbr:g[src]) {
if(nbr.first==par || nbr.second>w)continue;
if(vis[nbr.first])ans=1;
else dfs(nbr.first,src,w);
}
}
bool ok(int x,int y,int w){
int n=g.size();
for(int i=0; i<n; i++)
vis[i]=false;
ans=0;
dfs(x,-1,w);
if(!vis[y])return 0;
return ans;
}
int starr(int X,int Y){
if(X>Y)swap(X,Y);
int n=g.size();
if(n<=3)return -1;
if(X==0){
if(E[0][2]==Y || E[1][2]==Y)
return E[2][0];
else return g[Y][0].second;
}
else{
if(E[0][2]==X && E[1][2]==Y)
return E[2][0];
else if(E[0][2]==Y && E[1][2]==X)
return E[2][0];
else
return max(g[X][0].second,g[Y][0].second);
}
}
int getMinimumFuelCapacity(int X, int Y){
if(line)return -1;
else if(cyc)return mx-1;
else if(star)return starr(X,Y);
ll l=1,r=mx,ans=-1;
int n=g.size();
dsu d(n);
for(int i=0; i<E.size(); i++){
d.unite(E[i][1],E[i][2]);
if(d.get(X)==d.get(Y) && !d.is_line[d.get(X)])
return E[i][0];
}
return -1;
}
