問題一覧 > 通常問題

No.1194 Replace

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 64
作問者 : definedefine / テスター : ThistleThistle
3 ProblemId : 4900 / 出題時の順位表
問題文最終更新日: 2020-08-22 11:48:02

問題文

整数からなる長さ $N$ の数列 $A$ があります。初期状態では、$A_i\ = i $ です $(1 \leq i \leq N)$ 。

この数列に対して $M$ 個の操作候補があります。

$i$ 番目の操作 :
$A_j\ =\ B_i$ となる全ての $j$ について、$A_j\ =\ C_i$ に置き換える

どの操作にも回数制限はなく、一度も行わない操作があっても構いません。
また、操作はどの順番で行っても構わない他、一連の操作はいつ終了しても構いません。

一連の操作を終えた後、$A$ の要素の総和として考えられる最大値はいくつですか?

入力

$N\ M$
$B_1\ C_1$
$\cdots$
$B_M\ C_M$

$2 \leq N \leq 10^9$
$1 \leq M \leq 2 \times 10^5$
$1 \leq B_i,C_i \leq N$
$B_i \neq C_i$

入力は全て整数である。

出力

操作後の $A$ の要素の総和の最大値を1行に出力して下さい。

サンプル

サンプル1
入力
5 5
2 3
1 2
4 5
3 4
5 4
出力
25

操作前 : ${1,2,3,4,5}$
操作2 : ${2,2,3,4,5}$
操作1 : ${3,3,3,4,5}$
操作4 : ${4,4,4,4,5}$
操作3 : ${5,5,5,5,5}$

このようにして、全ての要素を5にする事ができます。

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

一度も操作をしなくても構いません。

サンプル3
入力
3 3
1 2
2 3
3 1
出力
9

同じ操作を何度しても構いません。

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