問題一覧 > 通常問題

No.1293 2種類の道路

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 94
作問者 : 沙耶花沙耶花 / テスター : tatyamtatyam
17 ProblemId : 3941 / 出題時の順位表
問題文最終更新日: 2020-09-29 23:33:30

問題文

沙耶花の暮らす国には $N$ 個の都市があります.
また, 都市と都市をつなぐ $D$ 本の自動車専用道路と $W$ 本の歩行者専用道路があります.
$i$ 番目の自動車専用道路は都市 $a_i$ と $b_i$ を相互に通行可能にしています.
同様に, $i$ 番目の歩行者専用道路は都市 $c_i$ と $d_i$ を相互に通行可能にしています.

次の条件を満たす整数の組 $(u,v)\,(1 \le u,v \le N,u \ne v)$ の個数を求めてください.

  • 0本以上の自動車専用道路と0本以上の歩行者専用道路をこの順に通ることで都市 $u$ から都市 $v$ に移動できる

入力

$N \ D \ W$
$a_1\  b_1$
$\vdots$
$a_{D}\  b_{D}$
$c_1\  d_1$
$\vdots$
$c_{W} \ d_{W}$

  • $2 \le N \le 10^5$
  • $1 \le D,W \le \min\left(10^5,\frac{N(N-1)}{2}\right)$
  • $1 \le a_i < b_i \le N$
  • $i \ne j$ ならば $(a_i,b_i) \ne (a_j,b_j)$
  • $1 \le c_i < d_i \le N$
  • $i \ne j$ ならば $(c_i,d_i) \ne (c_j,d_j)$
  • 入力はすべて整数

出力

答えを出力してください.
最後に改行してください.

サンプル

サンプル1
入力
4 2 1
1 2
2 3
2 4
出力
10

$(u,v)=(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,2)$ が該当します.

サンプル2
入力
10 5 5
1 2
1 3
1 4
2 4
3 7
3 8
2 4
1 3
9 10
1 10
出力
47

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。