No.3512 moesode
タグ : / 解いたユーザー数 49
作問者 :
Germanium32
/ テスター :
yt142857
Problem Statement
You are given a simple directed graph with $N$ vertices and $M$ edges. The vertices are numbered from $1$ to $N$, and the $i$-th edge goes from $A_i$ to $B_i$.
Now, suppose you add some directed edges to this graph so that the following condition is satisfied. What is the minimum number of edges to add?
Condition: The resulting graph is also a simple directed graph. In addition, for every vertex, if there exists an edge going out of that vertex, then the number of edges coming into that vertex is at least $K$.
Input
The input is given from standard input in the following format.
$N$$\ $$M$$\ $$K$ $A_1\ B_1$ $\vdots$ $A_M\ B_M$
- $2\leqq $ $ N $ $ \leqq2×10^5$
- $1\leqq $ $ M $ $ \leqq$ $\mathrm{min}$$(2×10^5,N(N-1))$
- $1\leqq $ $ K $ $\leqq N-1$
- $1\leqq $ $A_i$ $\leqq N$
- $1\leqq $ $B_i$ $\leqq N$
- $A_i \ne B_i$
- No pair $(A_i,B_i)$ appears more than once. That is, for every pair $(i,j)$ satisfying $1\leqq $ $ i $ $ < $ $ j $ $ \leqq $ $ M$, $A_i $ $ \ne $ $ A_j$ or $B_i $ $ \ne $ $ B_j$ holds.
- All inputs are integers.
Output
Output the answer.
Sample
Sample 1
Input
3 1 1
1 2
Output
1
Sample 2
Input
3 2 2
1 2
2 3
Output
4
Sample 3
Input
9 6 5
2 5
5 8
7 6
1 2
1 3
5 7
Output
25
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。