/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
頂点に 1 から N の、辺に 1 から M の番号がついた N 頂点 M 辺の無向グラフが与えられます。辺 i は頂点 u_i と頂点 v_i を結ぶ辺です。
グラフから辺を取り除いてグラフを単純にするためには、少なくとも何本の辺を取り除く必要がありますか？
ここでグラフが単純であるとは、グラフが自己ループや多重辺を含まないことをいいます。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 5 \times 10^5
- 1 \leq u_i \leq N
- 1 \leq v_i \leq N
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
出力
グラフを単純にするために取り除く必要がある辺の本数の最小値を出力せよ。
入力例 1
3 5 1 2 2 3 3 2 3 1 1 1
出力例 1
2
辺 3 と辺 5 を取り除くとグラフを単純にすることが出来て、これが取り除く辺の本数が最小となる選び方の 1 つです。よって答えは 2 本です。
入力例 2
1 0
出力例 2
0
入力例 3
6 10 6 2 4 1 5 1 6 6 5 3 5 1 1 4 6 4 4 2 5 6
出力例 3
3
Score : 300 points
Problem Statement
You are given an undirected graph with N vertices and M edges, where the vertices are numbered 1 through N and the edges are numbered 1 through M. Edge i connects vertices u_i and v_i.
To make the graph simple by removing edges, what is the minimum number of edges that must be removed?
Here, a graph is called simple if and only if it does not contain self-loops or multi-edges.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 5 \times 10^5
- 1 \leq u_i \leq N
- 1 \leq v_i \leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
Output
Print the minimum number of edges that must be removed to make the graph simple.
Sample Input 1
3 5 1 2 2 3 3 2 3 1 1 1
Sample Output 1
2
By removing edges 3 and 5, the graph becomes simple. This is one of the ways to remove the minimum number of edges, so the answer is 2.
Sample Input 2
1 0
Sample Output 2
0
Sample Input 3
6 10 6 2 4 1 5 1 6 6 5 3 5 1 1 4 6 4 4 2 5 6
Sample Output 3
3