스택 머신

스택 머신은 특별한 버스이다. 문이 앞쪽에 하나뿐이고 폭이 매우 좁아 승객끼리 서로 지나칠 수 없다. 따라서 가장 마지막에 탄 승객이 가장 먼저 내려야 하며, 승객들은 스택처럼(후입선출) 움직인다.

버스는 교차로들이 일방통행 도로로 연결된 도시를 달린다. 도로 하나를 지날 때마다 정확히 한 명의 승객이 타거나 내린다. 각 도로마다 그 승객의 키가 정해져 있으며, 키가 같은 승객이 여러 명 있을 수도 있다.

경로는 버스가 지나는 도로들의 순서이다. 버스는 경로의 시작과 끝에서 비어 있어야 하고, 승객이 내릴 때는 항상 스택의 맨 위에 있는 승객(그 키가 해당 도로에 정해진 키와 같아야 한다)이 내려야 한다. 주어진 교차로 사이를 잇는 경로를 계획하라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 세 정수 $N$, $M$, $Q$가 주어지며, 각각 교차로의 수($1 \le N \le 100$), 도로의 수($1 \le M \le 100000$), 질의의 수($1 \le Q \le 100000$)이다. 교차로는 $1$번부터 $N$번까지 번호가 매겨진다. 이어지는 $M$개의 줄에는 각각 세 정수 $X$, $Y$, $Z$가 주어진다. 이는 교차로 $X$에서 $Y$로 가는 일방통행 도로가 있고, $Z > 0$이면 키가 $Z$cm인 승객이 타며, $Z < 0$이면 키가 $-Z$cm인 승객이 내린다는 뜻이다. 모든 승객의 키는 $40$cm 이상 $220$cm 이하이다. 이어지는 $Q$개의 줄에는 각각 두 정수, 즉 경로의 시작 교차로와 끝 교차로가 주어진다.

각 질의마다, 버스가 시작 교차로에서 빈 상태로 출발해 끝 교차로에 빈 상태로 도착하는, 비어 있지 않은 최단 경로의 길이(도로의 수)를 한 줄에 출력한다. 그러한 경로가 존재할 때 그 길이는 $10^9$ 이하임이 보장된다. 그런 경로가 없으면 impossible을 출력한다.