Description

You do not know the results of the race, but Byteasar will tell you partial information. Now, you are asked to answer: what is the maximum number of distinct finishing times that all participants can have without violating his conditions? Some of them may tie (i.e., finish at the same time), and such ties count as one distinct time.

Byteasar tells you that all finishing times are integer seconds. He will also provide some relations between the participants’ times. Specifically, he will give you some pairs $(A, B)$, meaning that $A$’s time is exactly $1$ second less than $B$’s; and some pairs $(C, D)$, meaning that $C$’s time is not greater than $D$’s. Your task is to compute the maximum possible number of distinct finishing times for all participants that satisfies these conditions.

Please write a program to solve this puzzle.

Input Format

The first line contains three integers $n, m_{1}, m_{2}$, denoting the number of participants, the number of pairs $(A, B)$, and the number of pairs $(C, D)$, respectively.

The next $m_{1}$ lines each contain two integers $a_{i}, b_{i}$ ($a_{i} \ne b_{i}$). This means participant $a_{i}$’s time is exactly $1$ second less than participant $b_{i}$’s.

The next $m_{2}$ lines each contain two integers $c_{i}, d_{i}$ ($c_{i} \ne d_{i}$). This means participant $c_{i}$’s time is not greater than participant $d_{i}$’s.

Output Format

If there is a solution, output a single integer on one line, representing the maximum number of distinct finishing times among all participants.
If there is no solution, output NIE.

4 2 2
1 2
3 4
1 4
3 1

3

Hint

The answer is $3$, with $t_3 = 1$, $t_1 = t_4 = 2$, $t_2 = 3$.
($t_i$ denotes the time spent by participant $i$.)

Constraints

• For $15\%$ of the testdata, $n \le 10$.
• For $100\%$ of the testdata, $2 \le n \le 600$, $1 \le m_{1} + m_{2} \le 10^{5}$.

Translated by ChatGPT 5