1 /**************************************************************  2     Problem: 3732  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:268 ms  7     Memory:4412 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <algorithm> 12   13 using namespace std; 14 const int N = 16005; 15 const int M = 30005; 16   17 struct Edge { 18     int x, y, v; 19       20     inline bool operator < (const Edge &x) const { 21         return v < x.v; 22     } 23 } E[M]; 24   25 struct edge { 26     int next, to, v; 27     edge() {} 28     edge(int _n, int _t, int _v) : next(_n), to(_t), v(_v) {} 29 } e[M]; 30   31 struct tree_node { 32     int fa[16], mx[16], dep; 33 } tr[N]; 34   35 int n, m; 36 int fa[N]; 37 int tot, first[N]; 38   39 inline int read() { 40     int x = 0; 41     char ch = getchar(); 42     while (ch < ‘0‘ || ‘9‘ < ch) 43         ch = getchar(); 44     while (‘0‘ <= ch && ch <= ‘9‘) { 45         x = x * 10 + ch - ‘0‘; 46         ch = getchar(); 47     } 48     return x; 49 } 50   51 inline void Add_Edges(int x, int y, int v) { 52     e[++tot] = edge(first[x], y, v), first[x] = tot; 53     e[++tot] = edge(first[y], x, v), first[y] = tot; 54 } 55   56 int find_fa(int x) { 57     return x == fa[x] ? x : fa[x] = find_fa(fa[x]); 58 } 59   60 void Kruskal() { 61     int i, cnt, fa1, fa2; 62     sort(E + 1, E + m + 1); 63     for (i = 1; i <= n; ++i) 64         fa[i] = i; 65     for (i = 1, cnt = 0; i <= m; ++i) { 66         fa1 = find_fa(E[i].x), fa2 = find_fa(E[i].y); 67         if (fa1 != fa2) { 68             fa[fa1] = fa2, ++cnt; 69             Add_Edges(E[i].x, E[i].y, E[i].v); 70             if (cnt == n - 1) break; 71         } 72     } 73 } 74   75 void dfs(int p) { 76     int x, y; 77     for (x = 1; x < 16; ++x) { 78         tr[p].fa[x] = tr[tr[p].fa[x - 1]].fa[x - 1]; 79         tr[p].mx[x] = max(tr[p].mx[x - 1], tr[tr[p].fa[x - 1]].mx[x - 1]); 80     } 81     for (x = first[p]; x; x = e[x].next) 82         if ((y = e[x].to) != tr[p].fa[0]) { 83             tr[y].dep = tr[p].dep + 1; 84             tr[y].fa[0] = p, tr[y].mx[0] = e[x].v; 85             dfs(y); 86         } 87 } 88   89 int query(int x, int y) { 90     int res = 0, i; 91     if (tr[x].dep < tr[y].dep) swap(x, y); 92     for (i = 15; ~i; --i) 93         if (tr[tr[x].fa[i]].dep >= tr[y].dep) { 94             res = max(res, tr[x].mx[i]); 95             x = tr[x].fa[i]; 96         } 97     for (i = 15; ~i; --i) 98         if (tr[x].fa[i] != tr[y].fa[i]) { 99             res = max(res, max(tr[x].mx[i], tr[y].mx[i]));100             x = tr[x].fa[i], y = tr[y].fa[i];101         }102     if (x != y)103         res = max(res, max(tr[x].mx[0], tr[y].mx[0]));104     return res;105 }106  107 int main() {108     n = read(), m = read();109     int Q = read(), i, x, y;110     for (i = 1; i <= m; ++i)111         E[i].x = read(), E[i].y = read(), E[i].v = read();112     Kruskal();113     tr[1].dep = 1;114     dfs(1);115     while (Q--) {116         x = read(), y = read();117         printf("%d\n", query(x, y));118     }119     return 0;120 }