#include <iostream>
#include "swap.h"
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <limits.h>
#include <cassert>
#define fr first
#define sc second
using namespace std;
// #define int long long
const int N = 500005;
int dsu[N], par[23][N], valid[N], sz[N], zero[N], one[N], two[N], deg[N], val[N], depth[N];
int new_vertex;
vector<int> adj[N];
int find(int a)
{
if(dsu[a] == a)
{
return a;
}
return dsu[a] = find(dsu[a]);
}
void add_edge(int a, int b, int w)
{
int ca = find(a);
int cb = find(b);
if(ca == cb)
{
dsu[new_vertex] = new_vertex;
par[0][ca] = new_vertex;
dsu[ca] = new_vertex;
adj[new_vertex].push_back(ca);
val[new_vertex] = w;
if(valid[ca])
{
valid[new_vertex] = 1;
}
sz[new_vertex] = sz[ca];
zero[new_vertex] = zero[ca];
one[new_vertex] = one[ca];
two[new_vertex] = two[ca];
if(deg[a] == 2 || deg[b] == 2)
{
valid[new_vertex] = 1;
new_vertex++;
return;
}
if(deg[a] == 0)
{
deg[a]++;
zero[new_vertex]--;
one[new_vertex]++;
}
else if(deg[a] == 1)
{
deg[a]++;
one[new_vertex]--;
two[new_vertex]++;
}
if(deg[b] == 0)
{
deg[b]++;
zero[new_vertex]--;
one[new_vertex]++;
}
else if(deg[b] == 1)
{
deg[b]++;
one[new_vertex]--;
two[new_vertex]++;
}
if(two[new_vertex] == sz[new_vertex])
{
valid[new_vertex] = 1;
}
new_vertex++;
return;
}
dsu[new_vertex] = new_vertex;
dsu[ca] = new_vertex;
dsu[cb] = new_vertex;
par[0][ca] = new_vertex;
par[0][cb] = new_vertex;
adj[new_vertex].push_back(ca);
adj[new_vertex].push_back(cb);
val[new_vertex] = w;
if(valid[ca] || valid[cb])
{
valid[new_vertex] = 1;
}
else
{
if(deg[a] == 2 || deg[b] == 2)
{
valid[new_vertex] = 1;
new_vertex++;
return;
}
sz[new_vertex] = sz[ca]+sz[cb];
zero[new_vertex] = zero[ca]+zero[cb];
one[new_vertex] = one[ca]+one[cb];
two[new_vertex] = two[ca]+two[cb];
if(deg[a] == 0)
{
deg[a]++;
zero[new_vertex]--;
one[new_vertex]++;
}
else if(deg[a] == 1)
{
deg[a]++;
one[new_vertex]--;
two[new_vertex]++;
}
if(deg[b] == 0)
{
deg[b]++;
zero[new_vertex]--;
one[new_vertex]++;
}
else if(deg[b] == 1)
{
deg[b]++;
one[new_vertex]--;
two[new_vertex]++;
}
if(two[new_vertex] == sz[new_vertex])
{
valid[new_vertex] = 1;
}
}
new_vertex++;
}
void dfs(int u)
{
for(auto v : adj[u])
{
depth[v] = depth[u]+1;
dfs(v);
}
}
int jump(int a, int len)
{
for(int i = 0; i <= 19; i++)
{
if((len&(1<<i)) != 0)
{
a = par[i][a];
}
}
return a;
}
int lca_v(int a, int b)
{
// cout << "FINDING LCA: " << a << " " << b << endl;
int lca;
if(depth[a] < depth[b])
{
swap(a, b);
}
a = jump(a, depth[a]-depth[b]);
if(a == b){lca = a;}
else
{
// cout << "BEFORE ENTERING: " << a << " " << b << endl;
for(int i = 19; i >= 0; i--)
{
if(par[i][a] != par[i][b])
{
a = par[i][a];
b = par[i][b];
}
}
lca = par[0][a];
}
// cout << "LCA FOUND BEFORE VALID: " << lca << endl;
if(valid[lca])
{
return lca;
}
for(int i = 19; i >= 0; i--)
{
if(valid[par[i][lca]] == 0)
{
lca = par[i][lca];
}
}
lca = par[0][lca];
return lca;
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w)
{
for(int i = 1; i <= n; i++)
{
zero[i] = 1;
sz[i] = 1;
dsu[i] = i;
}
new_vertex = n+1;
vector<pair<int, int> > s;
for(int i = 0; i < m; i++)
{
s.push_back(make_pair(w[i], i));
}
sort(s.begin(), s.end());
for(int i = 0; i < m; i++)
{
//cout << "ADDING EDGE: " << u[s[i].sc]+1 << " " << v[s[i].sc]+1 << " " << s[i].fr << endl;
add_edge(u[s[i].sc]+1, v[s[i].sc]+1, s[i].fr);
}
// for(int i = 0; i < new_vertex; i++)
// {
// cout << "VALID[" << i << "] = " << valid[i] << endl;
// }
if(valid[new_vertex-1])
{
valid[0] = 1;
}
depth[0] = -1;
dfs(new_vertex-1);
// for(int i = 0; i < new_vertex; i++)
// {
// cout << "Depth[" << i << "] = " << depth[i] << endl;
// }
for(int i = 1; i <= 19; i++)
{
for(int j = 1; j < new_vertex; j++)
{
par[i][j] = par[i-1][par[i-1][j]];
}
}
// cout << new_vertex << endl;
}
int getMinimumFuelCapacity(int x, int y)
{
x++;
y++;
int bruh = lca_v(x, y);
if(bruh == 0)
{
return -1;
}
else
{
return val[bruh];
}
}
// int32_t main()
// {
// ios_base::sync_with_stdio(false);cin.tie(0);
// int n, m, q;
// cin >> n >> m;
// vector<int> u(m), v(m), w(m);
// for(int i = 0; i < m; i++)
// {
// cin >> u[i];
// }
// for(int i = 0; i < m; i++)
// {
// cin >> v[i];
// }
// for(int i = 0; i < m; i++)
// {
// cin >> w[i];
// }
// init(n, m, u, v, w);
// cin >> q;
// for(int i = 0; i < q; i++)
// {
// int x, y;
// cin >> x >> y;
// cout << getMinimumFuelCapacity(x, y) << endl;
// }
// }
/*
5 6
0 0 1 1 1 2
1 2 2 3 4 3
4 4 1 2 10 3
3
1 2
2 4
0 1
*/
/*
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <cassert>
*/
