자매 도시

인도네시아에는 $N$개의 도시가 있고, 0부터 $N-1$까지 번호가 매겨져 있다. 또 $M$개의 양방향 도로가 있고, 0부터 $M-1$까지 번호가 매겨져 있다. 각 도로는 서로 다른 두 도시를 잇는다. $i$번 도로는 $U_i$번 도시와 $V_i$번 도시를 잇고, 이 도로를 자동차로 달리려면 휘발유 $W_i$가 필요하다. 어떤 두 도시든지 도로를 따라 서로 오갈 수 있도록 도로망이 구축되어 있다.

앞으로 $Q$일 동안 매일 한 쌍의 도시가 자매 도시 관계를 맺으려고 한다. $j$번째 날에는 $X_j$번 도시가 $Y_j$번 도시와 자매 도시 관계를 맺으려고 한다. 이를 위해 $X_j$번 도시는 대표단을 자동차에 태워 $Y_j$번 도시로 보내고, $Y_j$번 도시도 대표단을 자동차에 태워 $X_j$번 도시로 보낸다.

혼잡을 막기 위해 두 자동차는 절대 마주치면 안 된다. 구체적으로, 두 자동차가 같은 시각에 같은 도시에 있으면 안 된다. 또 같은 도로를 동시에 서로 반대 방향으로 달려서도 안 된다. 어떤 도로에 들어선 자동차는 그 도로의 끝까지 가서 목적지에 도착해야 한다. 다시 말해 도로 중간에서는 유턴할 수 없다. 다만 자동차는 같은 도시나 같은 도로를 두 번 이상 지날 수 있다. 또 자동차는 언제든지 어떤 도시에서든지 대기할 수 있다.

연료 탱크가 큰 자동차는 비싸므로, 두 도시는 사용할 두 자동차의 연료 탱크 최대 용량을 최소화하는 경로를 택하고 싶어 한다. 각 도시에는 휘발유를 무한히 공급하는 주유소가 있다. 따라서 자동차에 필요한 연료 탱크의 최대 용량은, 그 자동차가 이용하는 모든 도로에서 필요한 휘발유 양 중 최댓값이다.

• $2 \le N \le 100000$.
• $N-1 \le M \le 200000$.
• $0 \le U_i < V_i < N$.
• 두 도시를 잇는 도로는 최대 1개이다.
• 어떤 두 도시든지 하나 또는 둘 이상의 도로를 이용하여 오갈 수 있다.
• $1 \le W_i \le 10^9$.
• $1 \le Q \le 200000$.
• $0 \le X_j < Y_j < N$.