#include <bits/stdc++.h>
#include "swap.h"
#define DIM 200010
#define INF 2000000000
using namespace std;
struct muchie{
int x,y,cost;
} mch[DIM];
vector<pair <int,int> > L[DIM];
vector <int> edg[DIM],a[DIM];
pair <int,int> rmq[20][DIM*3];
int t[DIM],ok[DIM],g[DIM],dp[DIM],p[DIM],level[DIM],E[DIM*3],first[DIM],g2[DIM];
int n,m,subtask,maxi,k;
inline int cmp (muchie a, muchie b){
return a.cost < b.cost;
}
inline int get_rad (int x){
while (t[x] > 0)
x = t[x];
return x;
}
void dfs (int nod, int tata){
E[++k] = nod;
first[nod] = k;
level[nod] = 1 + level[tata];
for (auto vecin : edg[nod]){
if (vecin != tata){
dfs (vecin,nod);
E[++k] = nod;
}
}
}
inline int get_lca (int x, int y){
int posx = first[x], posy = first[y];
if (posx > posy)
swap (posx,posy);
int nr = p[posy-posx+1];
pair <int,int> sol = min (rmq[nr][posx], rmq[nr][posy-(1<<nr)+1]);
return E[sol.second];
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
int i,j,rad;
n = N, m = M;
for (int i=0;i<m;i++){
int x = U[i], y = V[i], cost = W[i];
x++, y++;
L[x].push_back(make_pair(y,cost));
L[y].push_back(make_pair(x,cost));
maxi = max (maxi,cost);
mch[i+1] = {x,y,cost};
}
subtask = 1;
for (int i=1;i<=n;i++)
if (L[i].size() > 2)
subtask = 0;
sort (mch+1,mch+m+1,cmp);
for (int i=1;i<=n;i++){
t[i] = dp[i] = -1;
ok[i] = g[i] = g2[i] = 0;
a[i].push_back(i);
}
for (int i=1;i<=m;i++){
int x = mch[i].x, y = mch[i].y;
int radx = get_rad(x), rady = get_rad(y);
if (radx != rady){
if (t[radx] > t[rady])
swap (radx, rady);
if (!ok[radx] && ok[rady]){
for (auto it : a[radx])
dp[it] = mch[i].cost;
ok[radx] = i;
}
if (ok[radx] && !ok[rady]){
for (auto it : a[rady])
dp[it] = mch[i].cost;
ok[rady] = i;
}
for (auto it : a[rady])
a[radx].push_back(it);
a[rady].clear();
t[radx] += t[rady];
t[rady] = radx;
g[x]++, g[y]++;
if (g[x] >= 3 || g[y] >= 3){
if (!ok[radx]){
ok[radx] = i;
for (auto it : a[radx])
dp[it] = mch[i].cost;
}
}
} else {
/// o sa am un ciclu in componenta asta
if (!ok[radx]){
ok[radx] = i;
for (auto it : a[radx])
dp[it] = mch[i].cost;
}
}
//if (get_rad(X) == get_rad(Y) && ok[get_rad(X)])
// return mch[i].cost;
}
for (i=1;i<=n;i++)
if (!g2[i])
rad = i;
dfs (rad,0);
for (i=1;i<=k;i++)
rmq[0][i] = make_pair(level[E[i]],i);
for (i=1;(1<<i)<=k;i++)
for (j=1;j<=k;j++){
rmq[i][j] = rmq[i-1][j];
if (j + (1<<(i-1)) <= k && rmq[i-1][j + (1<<(i-1))].first < rmq[i][j].first)
rmq[i][j] = rmq[i-1][j + (1<<(i-1))];
}
for (i=2;i<=k;i++)
p[i] = p[i/2] + 1;
}
int getMinimumFuelCapacity(int X, int Y) {
if (subtask == 1){
if (m == n-1)
return -1;
else return maxi;
}
X++, Y++;
int maxim = max (dp[X],dp[Y]);
int lca = get_lca(X,Y);
maxim = max (maxim,mch[ok[lca]].cost);
if (maxim <= 0)
return -1;
else return maxim;
}
/*
int main (){
FILE *fin = fopen ("date.in", "r");
FILE *fout = fopen ("date.out", "w");
int N, M;
assert(2 == fscanf(fin, "%d %d", &N, &M));
std::vector<int> U(M), V(M), W(M);
for (int i = 0; i < M; ++i) {
assert(3 == fscanf(fin, "%d %d %d", &U[i], &V[i], &W[i]));
}
int Q;
assert(1 == fscanf(fin,"%d", &Q));
std::vector<int> X(Q), Y(Q);
for (int i = 0; i < Q; ++i) {
assert(2 == fscanf(fin,"%d %d", &X[i], &Y[i]));
}
init(N, M, U, V, W);
std::vector<int> minimum_fuel_capacities(Q);
for (int i = 0; i < Q; ++i) {
minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
}
for (int i = 0; i < Q; ++i) {
fprintf(fout, "%d\n", minimum_fuel_capacities[i]);
}
return 0;
}
*/
