#2788. [Poi2012]Festival

内存限制:64 MiB 时间限制:30 Sec

题目描述


有n个正整数X1,X2,...,Xn,再给出m1+m2个限制条件,限制分为两类:

1. 给出a,b (1<=a,b<=n),要求满足Xa + 1 = Xb

2. 给出c,d (1<=c,d<=n),要求满足Xc <= Xd

在满足所有限制的条件下,求集合{Xi}大小的最大值。



输入格式


第一行三个正整数n, m1, m2 (2<=n<=600, 1<=m1+m2<=100,000)。

接下来m1行每行两个正整数a,b (1<=a,b<=n),表示第一类限制。

接下来m2行每行两个正整数c,d (1<=c,d<=n),表示第二类限制。



输出格式

一个正整数,表示集合{Xi}大小的最大值。


如果无解输出NIE。

样例

样例输入


			
4 2 2

1 2

3 4

1 4

3 1

样例输出


			
3

数据范围与提示

|X3=1, X1=X4=2, X2=3


这样答案为3。容易发现没有更大的方案。