[AdditionalFile2689.zip](file://AdditionalFile2689.zip?type=additional_file)

#2689. 「POI2012 R1」节日 Festival

标签: 传统 | 时间限制: 7500 ms | 内存限制: 64 MiB |

题目描述

译自 POI 2012 Stage 1. 「Festival」

一次比赛中，$n$ 个运动员的耗时分别为 $X_1, X_2, \ldots, X_n$ 秒，且满足 $m_1 + m_2$ 个条件：

• 给定 $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)$ 类条件的个数。

接下来 $m_1$ 行每行两个整数 $a_i$ 和 $b_i$ 满足 $a_i \neq b_i$，表示第一类条件，即 $a_i$ 运动员比 $b_i$ 运动员耗时恰好少一秒。

接下来 $m_2$ 行每行两个整数 $c_i$ 和 $d_i$ 满足 $c_i \neq d_i$，表示第二类条件，即 $c_i$ 运动员耗时不长于 $d_i$ 运动员。

输出格式

输出一行一个整数，表示耗时不同的运动员的数量最大值。

如果没有符合条件的解，输出 NIE.

样例

输入

4 2 2
1 2
3 4
1 4
3 1

输出

3

有两种不同的可能：

• 三号运动员第一名，一、四号运动员并列第二名，二号运动员最后一名；
• 一、三号运动员并列第一名，二、四号运动员并列第二名。

数据范围与提示

对于 $15\%$ 的数据保证 $n \le 10$。

对于所有数据保证 $1 \le n \le 600,1 \le m_1 + m_2 \le 100\ 000$。