A charity festival is taking place in Byteburg, and you are one of the fundraisers. Unfortunately you have missed some fun activities, including a steeplechase. Byteasar, an amateur of puzzles, has promised a big donation if you manage to solve his riddle.

You do not know the results of the steeplechase but Byteasar has provided you with partial information. Now he is asking you what is the maximum possible (consistent with what he has told you) number of different times attained by the runners (some of them may have tied, i.e., reached the finish at the same time). Byteasar has told you that every runner's time is an integer multiple of one second. He has also provided you with relations between some of the runners' times. Specifically, he has given you some of the pairs of runners $(A,B)$ for which $A$’s time was exactly one second smaller than $B$’s time, and some of the pairs of runners $(C,D)$ for which $C$’s time was no larger than $D$’s time. Write a program that will solve the riddle for you!

Input

The first line of the standard input contains three non-negative integers, $n$, $m_1$, $m_2$ ($2 \le n \le 600$, $1 \le m_1 + m_2 \le 100\,000$), separated by single spaces, that denote respectively: the number of runners, the number of revealed pairs of the first type $(A,B)$, and the number of revealed pairs of the second type $(C,D)$. The runners are numbered from $1$ to $n$.

In the following $m_1$ lines the pairs of runners of the first kind are given, one per line - the $i$-th such line holds two integers $a_i$ and $b_i$, $a_i \ne b_i$, separated by a single space, that denote that runner ai’s time was exactly one second smaller than $b_i$’s.

In the next $m_2$ lines the pairs of runners of the second kind are given, one per line - the $i$-th such line holds two integers $c_i$ and $d_i$, $c_i \ne d_i$, separated by a single space, that denote that runner $c_i$’s time was no larger than $d_i$’s.

Output

In the first and only line of the standard output your program should print a single integer equal to the maximum possible number of different times attained by the runners consistent with the criteria.

If there is no order of runners satisfying Byteasar's constraints, the program should output a single line holding the word "NIE" (Polish for no), without the quotation marks.

In tests worth at least $15\%$ of points it additionally holds that $n \le 10$.

Example

For the input data:

4 2 2
1 2
3 4
1 4
3 1

the correct result is:

3

Explanation of the example: There were two possible outcomes of the chase:

1. runner no. 3 came first, the runners no. 1 and 4 shared the second place ex aequo, and the runner no. 2 came last;
2. runners no. 1 and 3 share the first place ex aequo, runners no. 2 and 4 share the second place ex aequo.

The first outcome gives three different times, more than the other.