uwiさんの提出を参考に定数倍高速化したら通った。

## solution

Use union-find tree. $O(mq\alpha(n))$.

Sort the available edges with the weight, then add them into the graph until it makes an odd-length cycle. When an odd-length cycle was made, the last edge’s weight is the answer.

The detection of the cycle can be done like the problem A of this problem set.

## implementation

#include <iostream>
#include <vector>
#include <algorithm>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) y) { return (f)(begin(y), end(y), ## __VA_ARGS__); })(x)
using namespace std;

struct disjoint_sets {
vector<int> data;
explicit disjoint_sets(size_t n) : data(n, -1) {}
bool is_root(int a) { return data[a] < 0; }
int find_root(int a) { return is_root(a) ? a : (data[a] = find_root(data[a])); }
int set_size(int a) { return - data[find_root(a)]; }
void union_sets(int a, int b) {
a = find_root(a); b = find_root(b);
if (a != b) {
if (set_size(a) > set_size(b)) swap(a,b);
data[b] += data[a];
data[a] = b;
}
}
bool is_same(int a, int b) { return find_root(a) == find_root(b); }
};

int main() {
int n, m, q; scanf("%d%d%d", &n, &m, &q);
vector<int> u(m), v(m), w(m);
repeat (i,m) {
scanf("%d%d%d", &u[i], &v[i], &w[i]);
-- u[i]; -- v[i];
}
vector<int> xs(m); whole(iota, xs, 0);
whole(sort, xs, [&](int x, int y) { return w[x] > w[y]; });
while (q --) {
int l, r; scanf("%d%d", &l, &r); -- l; -- r;
int ans = -1;
disjoint_sets t(2*n);
for (int x : xs) if (l <= x and x <= r) {
if (t.find_root(u[x]) == t.find_root(n+v[x])) continue; // required for the constant factor
t.union_sets(u[x], n+v[x]);
t.union_sets(v[x], n+u[x]);
if (t.is_same(u[x], v[x])) {
ans = w[x];
break;
}
}
printf("%d\n", ans);
}
return 0;
}