Problem : 153 - 運動會

Problem Statistics

Solved Member: 13　　Submission: 60　　User Tried: 15

Statement:

運動會到了！優秀的你被邀請來做田徑賽的裁判。

不料，由於你太不認真了，你忽然忘記了每個人賽跑所花的時間。你現在只知道一些關係存在：
1.(A,B)：A的秒數恰好比B少一秒
2.(C,D)：C的秒數不比D多

你知道某些這樣的關係，你想對所有人找出一種可能的排名，這些敘述中可能包含平手的情況。
不過你希望名次分的越細越好，你想知道，究竟最多有多少種「繞完一圈的時間」，來方便你對他們排名。

Input:Output:

輸入第一行有三個整數n,m1,m2(1 ≤ n ≤ 600; 1 ≤ m1+m2 ≤ 100000)，代表參賽者有 n 位(從1編號到n)，有m1種(A,B)的關係，m2種(C,D)的關係。
接下來的 m1 行每行有兩個數字(Ai,Bi)(Ai != Bi)，代表 Ai 的秒數恰好比 Bi 少一秒。
接下來的 m2 行每行有兩個數字(Ci,Di)(Ci != Di)，代表 Ci 的秒數不比 Di 多。

請輸出一行數字，代表最多能夠排出幾種名次。
如果找不出任何一種排名方案請輸出"NIE"。

Sample Input:Sample Output:

4 2 2
1 2
3 4
1 4
3 1

HINT:

有兩種可能的情況：
1. 3 號選手時間最快，1,4為第二名，2是第三名。
2. 1,3都是第一名，2,4都是第二名
不過第一種情況的名次最多，所以輸出3。

Source:

POI 19 Stage 1

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1-ocen	1000ms	65536kb
1-1	1000ms	65536kb	9
1-2	1000ms	65536kb
2-ocen	1000ms	65536kb
2-1	1000ms	65536kb	9
2-2	1000ms	65536kb
3-ocen	1000ms	65536kb
3-1	1000ms	65536kb	9
3-2	1000ms	65536kb
3-3	1000ms	65536kb
4-ocen	1000ms	65536kb
4-1	1000ms	65536kb	9
4-2	1000ms	65536kb
4-3	1000ms	65536kb
5-ocen	10000ms	65536kb
5-1	1000ms	65536kb	9
5-2	1000ms	65536kb
5-3	1000ms	65536kb
6-1	10000ms	65536kb	9
6-2	10000ms	65536kb
6-3	10000ms	65536kb
6-4	10000ms	65536kb
7-1	10000ms	65536kb	9
7-2	10000ms	65536kb
7-3	10000ms	65536kb
7-4	10000ms	65536kb
8-1	10000ms	65536kb	9
8-2	10000ms	65536kb
8-3	10000ms	65536kb
8-4	10000ms	65536kb
9-1	10000ms	65536kb	9
9-2	10000ms	65536kb
9-3	10000ms	65536kb
9-4	10000ms	65536kb
10-1	10000ms	65536kb	9
10-2	10000ms	65536kb
10-3	10000ms	65536kb
10-4	10000ms	65536kb
11-1	10000ms	65536kb	10
11-2	10000ms	65536kb
11-3	10000ms	65536kb
11-4	10000ms	65536kb