Maximum Distinct Finishing Times

In a cross‐country race, you do not know the final results, but Byteasar gives you partial information about the contestants' finishing times (in integer seconds). Specifically, he gives you two kinds of relations:

• For some pairs (A, B): contestant A finished exactly 1 second faster than contestant B, i.e. \(x_A = x_B - 1\).
• For some pairs (C, D): contestant C is not slower than contestant D, i.e. \(x_C \le x_D\).

Note that if some contestants finish at the same time (a tie), they are considered to have achieved the same finishing time.

Your task is to determine the maximum number of distinct finishing times that the contestants can have, while satisfying all of Byteasar’s conditions.

Input Format: The input consists of multiple test cases. The first line of input contains a single integer \(T\) representing the number of test cases. For each test case:

1. The first line contains three integers \(n, m, k\) where \(n\) is the number of contestants (numbered from 1 to \(n\)), \(m\) is the number of relations of the first type, and \(k\) is the number of relations of the second type.
2. The following \(m\) lines each contain two integers \(A\) and \(B\), indicating that contestant \(A\) finished exactly 1 second faster than contestant \(B\) (i.e. \(x_A = x_B - 1\)).
3. The next \(k\) lines each contain two integers \(C\) and \(D\), indicating that contestant \(C\) is not slower than contestant \(D\) (i.e. \(x_C \le x_D\)).

Output Format: For each test case, output a single integer — the maximum number of distinct finishing times that can be assigned to the contestants without contradicting any of the given conditions. It is guaranteed that the input conditions are consistent.

Explanation: The idea is to assign finishing times that satisfy all the equations and inequalities while maximizing the number of distinct times. Notice that the second type of relation (\(x_C \le x_D\)) forces contestants to tie if mutual relations exist (i.e. if \(x_C \le x_D\) and \(x_D \le x_C\), then \(x_C = x_D\)). Thus, one optimal strategy is to identify groups of contestants forced to tie (via cycles in the second type of relations) and assign each group a unique finishing time. The first type of relations naturally require consecutive distinct finishing times. Consequently, the answer equals the number of these groups.

inputFormat

The input begins with an integer \(T\) (\(1 \le T \le 10\)) on its own line representing the number of test cases. Each test case is described as follows:

 n m k
 A1 B1
 A2 B2
 ... (m lines for type-1 relations)
 C1 D1
 C2 D2
 ... (k lines for type-2 relations)

Here, \(n\) (\(1 \le n \le 10^5\)) is the number of contestants; each contestant is numbered from 1 to \(n\). For each type-1 relation, \(A\) and \(B\) (\(1 \le A, B \le n\)) denote that contestant \(A\)'s finishing time is exactly 1 second less than contestant \(B\)'s. For each type-2 relation, \(C\) and \(D\) denote that contestant \(C\)'s finishing time is not slower than contestant \(D\)'s (i.e. \(x_C \le x_D\)).

You can assume that the given conditions are consistent.

outputFormat

For each test case, print one integer: the maximum number of distinct finishing times that can be assigned to the contestants while respecting all conditions.

sample

3
3 1 1
1 2
2 3

3