4563 . 貳零貳參建北電資演算法小社賽 pC - Couple
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
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分
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~9 | $N \le 1000$ $Q \le 3000$ | 80 |
| 2 | 0~19 | 無其他限制 | 20 |
