#GYM104758H. Highly Resilient Network

Highly Resilient Network

本题没有可用的提交语言。

Description

Felix is an experienced systems administrator who takes information security in his network very seriously. Recently, he has set up a network of servers in his company, designed to be highly resilient to potential failures. To achieve this, Felix has connected every pair of servers in his network with high-speed connections.

Felix is aware that problems can occur at any time, and one or more connections might break due to failures or malicious attacks. However, he's particularly concerned about the possibility of exactly one connection failing.

To ensure that even if exactly one connection fails, there can still be uninterrupted communication between all servers in the network, Felix needs to know how many new connections he should add to the network at a minimum. Is possible that the initial network is not connected.

Your task is to help Felix calculate the minimum number of new connections he needs to add to his network to achieve his goal of high resilience in the event of exactly one connection failing.

An integer $N$ ($2 \leq N \leq 10^5$) representing the number of servers in the network. An integer $M$ ($1 \leq M \leq 10^5$) representing the current number of connections in the network. $M$ following lines, each containing two integers $A$ and $B$ ($1 \leq A, B \leq N$) indicating that servers $A$ and $B$ are currently connected.

An integer: the minimum number of new connections to be added to ensure connectivity in the event of exactly one connection failure.

Input

An integer $N$ ($2 \leq N \leq 10^5$) representing the number of servers in the network. An integer $M$ ($1 \leq M \leq 10^5$) representing the current number of connections in the network. $M$ following lines, each containing two integers $A$ and $B$ ($1 \leq A, B \leq N$) indicating that servers $A$ and $B$ are currently connected.

Output

An integer: the minimum number of new connections to be added to ensure connectivity in the event of exactly one connection failure.

5 4
1 2
2 3
3 4
4 5
3 3
1 2
2 3
3 1
4 1
1 2
1
0
3