题目描述

有 $n$ 个正整数 $x_{1\dots n}$，再给出 $m_1+m_2$ 个限制条件，限制分为两类：

1. 给出 $a,b$，要求满足 $x_a+1=x_b$。

2. 给出 $c,d$，要求满足 $x_c\leq x_d$。

在满足所有限制的条件下，求 $x_{1\dots n}$ 中最多有多少个不同的值。

输入格式

第一行三个正整数 $n,m_1,m_2$。
接下来 $m_1$ 行每行两个正整数 $a,b$，表示第一类限制。
接下来 $m_2$ 行每行两个正整数 $c,d$，表示第二类限制。

输出格式

一个正整数，表示 $x_{1\dots n}$ 中最多有多少个不同的值。
如果无解输出 NIE。

4 2 2
1 2
3 4
1 4
3 1

3

样例说明

$x_1=x_4=2,x_2=3,x_3=1$，这样答案为 $3$。
容易发现没有更大的方案。

数据规模与约定

对于 $100\%$ 的数据，$2\leq n\leq 600$，$1\leq m_1+m_2\leq 10^5$，$1\leq a,b,c,d\leq n$。