Festival

Problem Source

POI 2012

Problem Description

A charity event is being held in Byteburg, and you are one of the fundraisers. Unfortunately, you missed some interesting events, including a cross-country race.

The puzzle lover Byteasar promises that he will donate a large sum of money if you can solve his puzzle.

You do not know the result of the cross-country race, but Byteasar will tell you partial information. Now he asks you: what is the maximum number of different results all contestants can achieve without contradicting the conditions he gives? (Some of them may tie, i.e. arrive at the finish line at the same time; such a tie counts as only one result.)

Byteasar tells you that all contestants' results are integers in seconds. He also gives you some relations among contestants' results. Specifically: he gives you some pairs $(A, B)$ meaning $A$'s result is exactly $1$ second faster than $B$'s; and he gives you some pairs $(C, D)$ meaning $C$'s result is no slower than $D$'s (i.e. takes no more time). You must answer: what is the maximum number of different results all contestants can achieve without contradicting his 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 contestants, 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 \neq b_i$), meaning contestant $a_i$'s result is exactly $1$ second less than contestant $b_i$'s.

The next $m_2$ lines each contain two integers $c_i, d_i$ ($c_i \neq d_i$), meaning contestant $c_i$'s result is no worse than contestant $d_i$'s (takes no more time).

It is guaranteed that $2 \le n \le 600$ and $1 \le m_1 + m_2 \le 10^5$.

Output Format

If there is a solution, output one integer on a single line: the maximum number of different results all contestants can achieve. If there is no solution, output NIE.

Sample Input

4 2 2
1 2
3 4
1 4
3 1

Sample Output

3

Constraints

• $2 \le n \le 600$
• $1 \le m_1 + m_2 \le 10^5$