29800번 - The Decades of Coding Competitions 서브태스크다국어

문제

It has been almost 15ドル$ years since Sphinny became the premiere programming contestant by mastering the art of scheduling contests. She has grown alongside Coding Competitions and graduated into a programming contest organizer, and her Programming Club League (PCL) is the most popular sport in her city.

There are $\mathbf{N}$ bus stops in Sphinny's city, and $\mathbf{M}$ express bus routes. Each route bidirectionally connects two different bus stops, called their endpoints. Because of the popularity of PCL, the driver of each bus routes cheers for exactly one club.

Sphinny has to pick up the contest materials for the $j$-th contest at bus stop $\mathbf{P_j}$ and then the contest will be run in bus stop $\mathbf{C_j}$. She can only use the given bus routes to travel between them. Formally, a path for Sphinny to go from $\mathbf{P_j}$ to $\mathbf{C_j}$ is a list of bus routes such that each two consecutive routes have a common endpoint. Also the first route in the path has $\mathbf{P_j}$ as an endpoint and the last one has $\mathbf{C_j}$ as an endpoint. Notice that the same bus route can be used multiple times in a path. If Sphinny's path from $\mathbf{P_j}$ to $\mathbf{C_j}$ contains one or more bus routes whose driver cheers for club $c,ドル then club $c$ will join the contest. Otherwise, club $c$ will not join the contest. For organizational reasons, Sphinny needs the number of clubs in each contest to be an odd number.

Given the layout of Sphinny's city's bus routes and the contests' details, find out for how many contests there exists a path for Sphinny to take that can ensure an odd number of clubs joining it.

입력

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. The first line of each test case contains three integers $\mathbf{N},ドル $\mathbf{M},ドル and $\mathbf{Q}$: the number of bus stops, bus routes, and contests, respectively.

Then, $\mathbf{M}$ lines follow representing a different bus route each. The $i$-th of these lines contains three integers $\mathbf{U_i},ドル $\mathbf{V_i},ドル and $\mathbf{K_i},ドル meaning that the $i$-th bus route connects bus stops $\mathbf{U_i}$ and $\mathbf{V_i}$ and its driver cheers for club $\mathbf{K_i}$.

Finally, the last $\mathbf{Q}$ lines represent a contest each. The $j$-th of these lines contains two integers $\mathbf{P_j}$ and $\mathbf{C_j},ドル representing that materials for the $j$-th contest need to be picked up at bus stop $\mathbf{P_j}$ and the contest needs to be run at bus stop $\mathbf{C_j}$.

출력

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the number of contests for which Sphinny can find a path that ensures an odd number of clubs join it.

제한

• 1ドル \le \mathbf{T} \le 100$.
• 1ドル \le \mathbf{U_i} \le \mathbf{N},ドル for all $i$.
• 1ドル \le \mathbf{V_i} \le \mathbf{N},ドル for all $i$.
• $\mathbf{U_i} \neq \mathbf{V_i},ドル for all $i$
• $(\mathbf{U_i}, \mathbf{V_i}) \neq (\mathbf{U_j}, \mathbf{V_j})$ and $(\mathbf{U_i}, \mathbf{V_i}) \neq (\mathbf{V_j}, \mathbf{U_j}),ドル for all $i \neq j$. (No two bus routes have the same pair of endpoints.)
• 1ドル \le \mathbf{P_j} \le \mathbf{N},ドル for all $j$.
• 1ドル \le \mathbf{C_j} \le \mathbf{N},ドル for all $j$.
• $\mathbf{P_j} \neq \mathbf{C_j},ドル for all $j$.

Test Set 1 (7점)

시간 제한: 20 초

• 2ドル \le \mathbf{N} \le 500$.
• 1ドル \le \mathbf{M} \le 500$.
• 1ドル \le \mathbf{Q} \le 500$.
• 1ドル \le \mathbf{K_j} \le 2,ドル for all $j$.

Test Set 2 (6점)

시간 제한: 40 초

• 2ドル \le \mathbf{N} \le 500$.
• 1ドル \le \mathbf{M} \le 500$.
• 1ドル \le \mathbf{Q} \le 500$.
• 1ドル \le \mathbf{K_j} \le 100,ドル for all $j$.

Test Set 3 (10점)

시간 제한: 120 초

• 2ドル \le \mathbf{N} \le 10000$.
• 1ドル \le \mathbf{M} \le 10000$.
• 1ドル \le \mathbf{Q} \le 10000$.
• 1ドル \le \mathbf{K_j} \le 100,ドル for all $j$.

힌트