E - Wi-Fiアクセスポイントの設置 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君は、大学キャンパスのネットワーク管理者です。キャンパス内には N 個の建物と M 本の連絡通路があり、それぞれの建物には 1 から N までの番号が付けられています。i 番目の連絡通路は建物 u_i と建物 v_i を双方向に結んでいます。

このキャンパスの建物は「教育棟」と「研究棟」の2種類に分類されており、連絡通路はすべて異なる種類の建物の間を結んでいます。すなわち、建物と連絡通路からなるグラフは二部グラフです。ただし、各建物がどちらの種類に属するかは入力では与えられません。また、グラフは連結とは限りません。

大学の方針により、すべての連絡通路で Wi-Fi が利用できるようにしたいと考えています。ある建物に Wi-Fi アクセスポイントを設置すると、その建物を端点とするすべての連絡通路で Wi-Fi が利用可能になります。

高橋君は、すべての連絡通路について、その両端の建物のうち少なくとも一方にアクセスポイントが設置されている状態を実現したいです。この条件を満たすように選ぶ建物の数の最小値を求めてください。

制約

  • 1 \leq N \leq 10^5
  • 0 \leq M \leq 10^5
  • 1 \leq u_i, v_i \leq N
  • u_i \neq v_i（自己ループはない）
  • 同じ建物の組を結ぶ連絡通路は高々 1 本である（多重辺はない）
  • 与えられるグラフは二部グラフである
  • グラフは連結とは限らない
  • 入力はすべて整数である

入力

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M
  • 1 行目には、建物の数 N と連絡通路の数 M がスペース区切りで与えられる。
  • 続く M 行の i 行目 (1 \leq i \leq M) には、i 番目の連絡通路が結ぶ2つの建物の番号 u_i と v_i がスペース区切りで与えられる。

出力

すべての連絡通路で Wi-Fi を利用可能にするために、アクセスポイントを設置する建物の最小数を 1 行で出力してください。

入力例 1

4 4
1 2
2 3
3 4
4 1

出力例 1

2

入力例 2

5 4
1 2
1 3
1 4
1 5

出力例 2

1

入力例 3

10 8
1 6
1 7
2 7
2 8
3 8
3 9
4 9
5 10

出力例 3

5

入力例 4

8 16
1 5
1 6
1 7
1 8
2 5
2 6
2 7
2 8
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8

出力例 4

4

入力例 5

1 0

出力例 5

0

Score : 466 pts

Problem Statement

Takahashi is the network administrator of a university campus. The campus has N buildings and M corridors, and each building is numbered from 1 to N. The i-th corridor bidirectionally connects building u_i and building v_i.

The buildings on this campus are classified into two types: "educational buildings" and "research buildings," and every corridor connects buildings of different types. In other words, the graph consisting of buildings and corridors is a bipartite graph. However, which type each building belongs to is not given in the input. Also, the graph is not necessarily connected.

According to university policy, Wi-Fi should be available on all corridors. When a Wi-Fi access point is installed in a building, Wi-Fi becomes available on all corridors that have that building as an endpoint.

Takahashi wants to achieve a state where, for every corridor, at least one of the two buildings at its endpoints has an access point installed. Find the minimum number of buildings that need to be selected to satisfy this condition.

Constraints

  • 1 \leq N \leq 10^5
  • 0 \leq M \leq 10^5
  • 1 \leq u_i, v_i \leq N
  • u_i \neq v_i (no self-loops)
  • There is at most one corridor connecting the same pair of buildings (no multi-edges)
  • The given graph is a bipartite graph
  • The graph is not necessarily connected
  • All input values are integers

Input

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M
  • The first line contains the number of buildings N and the number of corridors M, separated by a space.
  • The i-th of the following M lines (1 \leq i \leq M) contains the numbers u_i and v_i of the two buildings connected by the i-th corridor, separated by a space.

Output

Print in one line the minimum number of buildings in which access points need to be installed to make Wi-Fi available on all corridors.

Sample Input 1

4 4
1 2
2 3
3 4
4 1

Sample Output 1

2

Sample Input 2

5 4
1 2
1 3
1 4
1 5

Sample Output 2

1

Sample Input 3

10 8
1 6
1 7
2 7
2 8
3 8
3 9
4 9
5 10

Sample Output 3

5

Sample Input 4

8 16
1 5
1 6
1 7
1 8
2 5
2 6
2 7
2 8
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8

Sample Output 4

4

Sample Input 5

1 0

Sample Output 5

0