Byteburg 正在举办一场慈善节，你是筹款人之一。不幸的是，你错过了一些有趣的活动，包括一场障碍赛。Byteasar 是一位谜题爱好者，他承诺如果你能解开他的谜题，他就会捐出一大笔钱。

你不知道障碍赛的结果，但 Byteasar 为你提供了一些部分信息。现在他问你，在符合他所告知信息的前提下，参赛者所取得的不同成绩数量的最大可能值是多少（有些人可能并列，即同时到达终点）。Byteasar 告诉你，每位参赛者的成绩都是一秒的整数倍。他还提供了部分参赛者成绩之间的关系。具体来说，他给出了若干对参赛者 $(A, B)$，表示 $A$ 的成绩比 $B$ 的成绩恰好少一秒；以及若干对参赛者 $(C, D)$，表示 $C$ 的成绩不大于 $D$ 的成绩。请编写一个程序来为你解开这个谜题！

标准输入的第一行包含三个非负整数 $n, m_1, m_2$（$2 \le n \le 600, 1 \le m_1 + m_2 \le 100\,000$），用空格分隔，分别表示：参赛者人数、第一类关系 $(A, B)$ 的数量以及第二类关系 $(C, D)$ 的数量。参赛者编号从 $1$ 到 $n$。

接下来的 $m_1$ 行，每行给出第一类关系，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$a_i \ne b_i$），用空格分隔，表示参赛者 $a_i$ 的成绩比 $b_i$ 的成绩恰好少一秒。

接下来的 $m_2$ 行，每行给出第二类关系，第 $i$ 行包含两个整数 $c_i$ 和 $d_i$（$c_i \ne d_i$），用空格分隔，表示参赛者 $c_i$ 的成绩不大于 $d_i$ 的成绩。

程序应在标准输出的第一行（也是唯一一行）打印一个整数，表示在符合条件的前提下，参赛者所取得的不同成绩数量的最大可能值。

如果不存在满足 Byteasar 约束的参赛者成绩排序，程序应输出一行包含单词 "NIE"（波兰语，意为“不”），不含引号。

在至少占 $15\%$ 分值的测试点中，满足 $n \le 10$。

样例

输入格式 1

4 2 2
1 2
3 4
1 4
3 1

输出格式 1

3

说明

该样例有两种可能的比赛结果：

1. 3 号选手获得第一名，1 号和 4 号选手并列第二名，2 号选手最后到达；
2. 1 号和 3 号选手并列第一名，2 号和 4 号选手并列第二名。

第一种结果产生了三种不同的成绩，多于第二种结果。