#P50790. 「POI2012」节日 Festival
「POI2012」节日 Festival
题目描述
译自 POI 2012 Stage 1. 「Festival」
一次比赛中, 个运动员的耗时分别为 秒,且满足 个条件:
- 给定 和 , 运动员比 运动员耗时恰好少一秒
- 给定 和 , 运动员耗时不长于 运动员
在符合条件的情况下,求所有运动员不同耗时总数的最大值。
输入格式
第一行三个非负整数 ,表示运动员个数、 类条件的个数和 类条件的个数。
接下来 行每行两个整数 和 满足 ,表示第一类条件,即 运动员比 运动员耗时恰好少一秒。
接下来 行每行两个整数 和 满足 ,表示第二类条件,即 运动员耗时不长于 运动员。
输出格式
输出一行一个整数,表示耗时不同的运动员的数量最大值。
如果没有符合条件的解,输出 NIE
.
样例
4 2 2
1 2
3 4
1 4
3 1
3
有两种不同的可能:
- 三号运动员第一名,一、四号运动员并列第二名,二号运动员最后一名;
- 一、三号运动员并列第一名,二、四号运动员并列第二名。
数据范围与提示
对于 的数据保证 。
对于所有数据保证 。