수십 년간의 코딩 대회

Sphinny가 대회 일정 관리 기술을 통달하여 최고의 프로그래밍 대회 참가자가 된 지 거의 $15$년이 지났다. 그녀는 Coding Competitions와 함께 성장하여 프로그래밍 대회 주최자가 되었고, 그녀의 Programming Club League장인 (PCL)는 그녀가 사는 도시에서 가장 인기 있는 스포츠이다.

Sphinny의 도시에는 $\mathbf{N}$개의 버스 정류장과 $\mathbf{M}$개의 급행 버스 노선이 있다. 각 노선은 양 끝점이라고 부르는 서로 다른 두 버스 정류장을 양방향으로 연결한다. PCL의 인기로 인해 각 버스 노선의 운전기사는 정확히 하나의 클럽을 응원한다.

Sphinny는 $j$번째 대회의 물품을 버스 정류장 $\mathbf{P_j}$에서 수령해야 하며, 그 후 대회는 버스 정류장 $\mathbf{C_j}$에서 진행된다. 그녀는 두 정류장 사이를 이동할 때 주어진 버스 노선만 이용할 수 있다. 형식적으로, Sphinny가 $\mathbf{P_j}$에서 $\mathbf{C_j}$로 가는 경로는 연속한 모든 두 노선이 공통 끝점을 갖는 버스 노선의 목록이다. 또한 경로의 첫 번째 노선은 $\mathbf{P_j}$를 끝점으로 가지며, 마지막 노선은 $\mathbf{C_j}$를 끝점으로 가진다. 같은 버스 노선을 한 경로에서 여러 번 이용할 수 있다는 점에 유의하라. Sphinny가 $\mathbf{P_j}$에서 $\mathbf{C_j}$로 가는 경로에 운전기사가 클럽 $c$를 응원하는 버스 노선이 하나 이상 포함되어 있다면, 클럽 $c$가 대회에 참가한다. 그렇지 않으면 클럽 $c$는 대회에 참가하지 않는다. 운영상의 이유로 Sphinny는 각 대회에 참가하는 클럽의 수가 홀수여야 한다.

Sphinny의 도시 내 버스 노선 배치와 대회 세부 정보가 주어질 때, Sphinny가 택할 수 있는 경로 중 홀수 개의 클럽이 참가하도록 보장하는 경로가 존재하는 대회의 수를 구하라.

제한

메모리 제한: 2 GB. $1 \le \mathbf{T} \le 100$. 모든 $i$에 대해, $1 \le \mathbf{U_i} \le \mathbf{N}$. 모든 $i$에 대해, $1 \le \mathbf{V_i} \le \mathbf{N}$. 모든 $i$에 대해, $\mathbf{U_i} \neq \mathbf{V_i}$ 모든 $i \neq j$에 대해, $(\mathbf{U_i}, \mathbf{V_i}) \neq (\mathbf{U_j}, \mathbf{V_j})$ 및 $(\mathbf{U_i}, \mathbf{V_i}) \neq (\mathbf{V_j}, \mathbf{U_j})$. (어떤 두 버스 노선도 끝점의 쌍이 같지 않다.) 모든 $j$에 대해, $1 \le \mathbf{P_j} \le \mathbf{N}$. 모든 $j$에 대해, $1 \le \mathbf{C_j} \le \mathbf{N}$. 모든 $j$에 대해, $\mathbf{P_j} \neq \mathbf{C_j}$.

테스트 세트 1 (Visible Verdict)

시간 제한: 20초. $2 \le \mathbf{N} \le 500$. $1 \le \mathbf{M} \le 500$. $1 \le \mathbf{Q} \le 500$. 모든 $j$에 대해, $1 \le \mathbf{K_j} \le 2$.

테스트 세트 2 (Visible Verdict)

시간 제한: 40초. $2 \le \mathbf{N} \le 500$. $1 \le \mathbf{M} \le 500$. $1 \le \mathbf{Q} \le 500$. 모든 $j$에 대해, $1 \le \mathbf{K_j} \le 100$.

테스트 세트 3 (Hidden Verdict)

시간 제한: 120초. $2 \le \mathbf{N} \le 10000$. $1 \le \mathbf{M} \le 10000$. $1 \le \mathbf{Q} \le 10000$. 모든 $j$에 대해, $1 \le \mathbf{K_j} \le 100$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 버스 정류장, 버스 노선, 대회의 수를 각각 나타내는 세 정수 $\mathbf{N}$, $\mathbf{M}$, $\mathbf{Q}$가 주어진다.

이어서 각각 서로 다른 버스 노선을 나타내는 $\mathbf{M}$개의 줄이 주어진다. 이 중 $i$번째 줄에는 세 정수 $\mathbf{U_i}$, $\mathbf{V_i}$, $\mathbf{K_i}$가 주어지며, 이는 $i$번째 버스 노선이 버스 정류장 $\mathbf{U_i}$와 $\mathbf{V_i}$를 연결하고 그 운전기사가 클럽 $\mathbf{K_i}$를 응원한다는 뜻이다.

마지막 $\mathbf{Q}$개의 줄은 각각 하나의 대회를 나타낸다. 이 중 $j$번째 줄에는 두 정수 $\mathbf{P_j}$와 $\mathbf{C_j}$가 주어지며, 이는 $j$번째 대회의 물품을 버스 정류장 $\mathbf{P_j}$에서 수령해야 하고 대회를 버스 정류장 $\mathbf{C_j}$에서 진행해야 한다는 뜻이다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 Sphinny가 홀수 개의 클럽이 참가하도록 보장하는 경로를 찾을 수 있는 대회의 수이다.

예제 케이스 #1은 위 그림에 나와 있다. 처음 두 대회에서는 어떤 경로를 선택하더라도 두 클럽(초록색과 파란색)이 모두 참가해야 한다. 마지막 대회에서는 버스 정류장 $1, 2, 4, 5$를 지나는 경로를 이용하여 초록색 클럽만 참가시키는 것이 가능하다.

예제 케이스 #2에서 첫 번째 대회는 버스 정류장 $1$에서 버스 정류장 $2$로 가는 경로가 없으므로 가능하지 않다. 두 번째 대회에는 버스 정류장 $1$에서 버스 정류장 $3$로 가는 유일한 버스 노선을 포함하는 경로가 있으므로, 정확히 $1$개의 클럽이 참가하는 대회가 되며 이는 허용되는 홀수 개의 클럽이다.

추가 예제 - 테스트 세트 2

이 추가 예제 케이스는 위 그림에 나와 있다. 이 경우 두 대회 모두 홀수 개의 클럽이 참가하도록 진행할 수 있다. 이를 달성하는 경로의 예가 그림에 나와 있다.