TopCoder

lemonilemon
學弟加電研!

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

58.6% (17/29)

Tags

Description

有兩個人,他們是一個couple
他們在玩一個遊戲
這個遊戲有N個關卡
想要去某個關卡會需要某些特定關卡的信物
當然也有些關卡沒有任何條件可以拿來開荒
因為大家都覺得準備充分是比較好的選擇
而關卡編號越小的關卡顯然是越簡單
所以如果同時有多個關卡都滿足要求
大家都會選擇關卡編號較小的那一個
還有因為這遊戲是一個給couple玩的遊戲
沒朋友的孤兒完全是一個玩不了的狀態
可杯
這遊戲唯一獲得分數的方式是兩個人在皆滿足關卡要求後通關
便能獲得一分然後可以繼續一起破關
或是分道揚鑣
那你也是笑的很開心想跟他女朋友一起玩這個遊戲
但是他們忙著放閃
所以請你計算他們能獲得的最高分數

Input Format

$N_1 \ M_1$
$u_{11} \ v_{11}$
$u_{12} \ v_{12}$
$...$
$u_{1m} \ v_{1m}$
$N_2 \ M_2$
$u_{21} \ v_{21}$
$u_{22} \ v_{22}$
$...$
$u_{2m} \ v_{2m}$

其中 $N \ M$ 代表共有幾關以及共有幾條約束關係
$N_1 \ N_2$ 分別代表第一位玩家與第二位玩家遊玩時所得到的約束關係
保證 $N_1 = N_2$
$N \le 100000$
$M \le 300000$
$0 \le u_i, v_i \lt N$
$u_i, v_i$代表想要通關 $v_i$ 必須先拿到 $u_i$ 的信物

Output Format

請輸出一非負整數告訴那你也是笑的很開心他能拿到幾分讓他更開心

Sample Input 1

10 10
3 2
4 5
4 9
5 0
6 0
6 2
7 2
7 3
8 3
8 9
10 10
0 3
0 4
0 9
2 3
5 9
6 4
6 5
8 0
8 1
8 9

Sample Output 1

7

Hints

對於第一筆測資
兩個人的通關順序依序為
1 4 5 6 0 7 8 3 9 2
2 6 5 7 8 0 1 3 4 9
可以一起通關拿到7分

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~9 $N \le 1000$ $Q \le 3000$ 80
2 0~19 無其他限制 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 250000 65536 1 2
1 1000 250000 65536 1 2
2 1000 250000 65536 1 2
3 1000 250000 65536 1 2
4 1000 250000 65536 1 2
5 1000 250000 65536 1 2
6 1000 250000 65536 1 2
7 1000 250000 65536 1 2
8 1000 250000 65536 1 2
9 1000 250000 65536 1 2
10 1000 250000 65536 2
11 1000 250000 65536 2
12 1000 250000 65536 2
13 1000 250000 65536 2
14 1000 250000 65536 2
15 1000 250000 65536 2
16 1000 250000 65536 2
17 1000 250000 65536 2
18 1000 250000 65536 2
19 1000 250000 65536 2