#include <bits/stdc++.h>
#include "swap.h"
#define DIM 200010
#define INF 2000000000
using namespace std;
struct muchie{
int x,y,cost;
} mch[DIM];
priority_queue <pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > h;
vector<pair <int,int> > L[DIM];
deque <int> c;
int dist[DIM],t[DIM],cnt[DIM],f[DIM],viz[DIM],mrk[DIM];
int n,m,subtask,maxi;
void dijkstra (int start, int dist[], int cnt[], int t[]){
for (int i=1;i<=n;i++){
dist[i] = INF;
cnt[i] = 0;
t[i] = 0;
}
while (!h.empty())
h.pop();
dist[start] = 0;
cnt[start] = 1;
h.push(make_pair(dist[start],start));
while (!h.empty()){
int nod = h.top().second, cost = h.top().first;
h.pop();
if (dist[nod] != cost)
continue;
for (auto it : L[nod]){
int vecin = it.first, cst = it.second;
if (dist[nod] + cst < dist[vecin]){
dist[vecin] = dist[nod] + cst;
cnt[vecin] = cnt[nod];
t[vecin] = nod;
h.push(make_pair(dist[vecin],vecin));
} else {
if (dist[nod] + cst == dist[vecin])
cnt[vecin] += cnt[nod];
}
}
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
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;
}
void dfs (int nod, int val){
viz[nod] = 1;
for (auto it : L[nod]){
if (it.second > val || mrk[it.first] || viz[it.first])
continue;
dfs (it.first,val);
}
}
inline int verif (int val, int x, int y){
memset (viz,0,sizeof viz);
memset (t,0,sizeof t);
memset (mrk,0,sizeof mrk);
c.clear();
c.push_back(x);
viz[x] = 1;
int ok = 0;
while (!c.empty()){
int nod = c.front();
c.pop_front();
int cnt = 0;
for (auto it : L[nod]){
int vecin = it.first, cost = it.second;
if (cost > val)
continue;
if (!viz[vecin]){
viz[vecin] = 1 + viz[nod];
t[vecin] = nod;
c.push_back(vecin);
}
cnt++;
}
if (cnt > 2 && nod != x && nod != y)
ok = 1;
}
if (!viz[y])
return 0;
if (ok)
return 1;
/// exista doua drumuri disjuncte intre x si y?
int nod = y;
while (nod){
if (nod != y)
mrk[nod] = 1;
nod = t[nod];
}
memset (viz,0,sizeof viz);
dfs (x,val);
if (viz[y])
return 1;
return 0;
}
int getMinimumFuelCapacity(int x, int y) {
if (subtask == 1){
if (m == n-1)
return -1;
else return maxi;
}
x++, y++;
int st = 1, dr = maxi, sol = -1;
while (st <= dr){
int mid = (st+dr)>>1;
if (verif(mid,x,y)){
sol = mid;
dr = mid-1;
} else st = mid+1;
}
return sol;
}
/*
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;
}*/
