1 && 3 그래프

세훈이와 찬우는 많은 그래프 문제를 풀면서 좋은 그래프 문제의 조건을 생각하게 되었다.

• 세훈이는 특별한 예외 처리가 필요하지 않은 일반적인 그래프가 주어져야 한다고 생각한다. 여기서 일반적인 그래프란 중복 간선이 없고, 모든 정점이 연결되어 있으며, 서로 다른 두 정점을 잇는 간선만 있는 무방향 그래프를 말한다.
• 찬우는 차수가 큰 정점이 많을수록 그래프가 복잡해진다고 생각한다. 구체적으로, 차수가 $3$ 이상인 정점의 개수는 $3$개 미만이어야 한다.

두 사람은 위 조건을 모두 만족하는 그래프를 1 && 3 그래프라고 부르기로 했다. 정점이 $V$개, 간선이 $E$개인 1 && 3 그래프가 주어진다. 두 정점 사이의 최단 거리를 묻는 쿼리 $Q$개를 처리하는 프로그램을 작성하라.

첫째 줄에 정점의 개수 $V$, 간선의 개수 $E$, 쿼리의 수 $Q$가 공백으로 구분되어 주어진다. $(2 \le V \le 500000; V-1 \le E \le 500000; 1 \le Q \le 200000)$

다음 $E$개의 줄에는 각 간선이 잇는 두 정점 $x$, $y$와 간선의 가중치 $c$가 공백으로 구분되어 주어진다. $(1 \le x,y \le V; 1 \le c \le 10^9; x \ne y)$

그 다음 $Q$개의 줄에는 두 정점 $a$, $b$가 공백으로 구분되어 주어진다. 이는 $a$번 정점과 $b$번 정점 사이의 최단 거리를 묻는 쿼리이다. $(1 \le a,b \le V)$

입력으로 주어지는 모든 수는 정수이며, 주어지는 그래프는 1 && 3 그래프이다.

$Q$개의 줄에 걸쳐 각 쿼리의 정답을 입력 순서대로 한 줄에 하나씩 출력한다.