7452: [POI 2012] FES-Festival
[Creator : ]
Description
题目背景
在 Byteburg 举办了一场慈善活动，你是其中一个筹款人。不幸的是，你错过了一些有趣的活动，包括一场越野赛。
谜题爱好者 Byteasar 承诺：如果你能解开他的谜题，他会捐一大笔钱。
题目描述
你不知道越野赛的结果，但 Byteasar 会告诉你部分信息。现在，他要你答出：所有参赛者最多能达到多少种不同的成绩，而不违背他给的条件。（他们中的一些人可能平局，也就是同时到达终点，这种情况只算有一种成绩）。
Byteasar 告诉你，所有参赛者的成绩都是整数秒。他还会为你提供了一些参赛者成绩的关系。具体是：他会给你一些数对 $(A, B)$，表示 $A$ 的成绩正好比 $B$ 快 $1$ 秒；他还会给你一些数对 $(C, D)$，表示 $C$ 的成绩比 $D$ 快。而你要回答的是：所有参赛者最多能达到多少种不同的成绩，而不违背他给的条件。
请你编程解决这个谜题。
在 Byteburg 举办了一场慈善活动，你是其中一个筹款人。不幸的是，你错过了一些有趣的活动，包括一场越野赛。
谜题爱好者 Byteasar 承诺：如果你能解开他的谜题，他会捐一大笔钱。
题目描述
你不知道越野赛的结果，但 Byteasar 会告诉你部分信息。现在，他要你答出：所有参赛者最多能达到多少种不同的成绩，而不违背他给的条件。（他们中的一些人可能平局，也就是同时到达终点，这种情况只算有一种成绩）。
Byteasar 告诉你，所有参赛者的成绩都是整数秒。他还会为你提供了一些参赛者成绩的关系。具体是：他会给你一些数对 $(A, B)$，表示 $A$ 的成绩正好比 $B$ 快 $1$ 秒；他还会给你一些数对 $(C, D)$，表示 $C$ 的成绩比 $D$ 快。而你要回答的是：所有参赛者最多能达到多少种不同的成绩，而不违背他给的条件。
请你编程解决这个谜题。
Input
第一行有三个整数 $n, m_{1}, m_{2}$，分别表示选手人数、数对 $(A, B)$ 的数目、数对 $(C, D)$ 的数目。
接下来 $m_1$ 行，每行两个整数 $a_{i}, b_{i}$（$a_{i} \ne b_{i}$）。这表示选手 $a_{i}$ 的成绩恰比 $b_{i}$ 小 $1$ 秒。
接下来 $m_{2}$ 行，每行两个整数 $c_{i}, d_{i}$（$c_{i} \ne d_{i}$）。这表示选手 $c_{i}$ 的成绩不比 $d_{i}$ 的成绩差（也就是花的时间不会更多）。
接下来 $m_1$ 行，每行两个整数 $a_{i}, b_{i}$（$a_{i} \ne b_{i}$）。这表示选手 $a_{i}$ 的成绩恰比 $b_{i}$ 小 $1$ 秒。
接下来 $m_{2}$ 行，每行两个整数 $c_{i}, d_{i}$（$c_{i} \ne d_{i}$）。这表示选手 $c_{i}$ 的成绩不比 $d_{i}$ 的成绩差（也就是花的时间不会更多）。
Output
如果有解，输出一行一个整数，表示所有选手最多能拿到的成绩的种数。
如果无解，输出 `NIE`。
如果无解，输出 `NIE`。
Constraints
对于 $15\%$ 的数据，$n \le 10$。
对于 $100\%$ 的数据，$2 \le n \le 600$，$1 \le m_{1} + m_{2} \le {10}^5$。
对于 $100\%$ 的数据，$2 \le n \le 600$，$1 \le m_{1} + m_{2} \le {10}^5$。
Sample 1 Input
4 2 2
1 2
3 4
1 4
3 1
Sample 1 Output
3
答案为 $3$，情况为：$t_3=1, t_1=t_4=2, t_2=3$。
（$t_i$ 表示参赛者 $i$ 花的时间）
（$t_i$ 表示参赛者 $i$ 花的时间）