Have you heard of a company called Just Odd Inventions? This company specializes just in odd inventions. We will call it JOI Corp for short.
In the JOI laboratories, there is a complex electrical circuit. The circuit consists of N nodes and M resistors. The nodes are numbered from 1 to N. Each node can be set to either the "high voltage" or the "low voltage" state. Each resistor connects two nodes and allows current to flow through it if it connects a "high voltage" node and a "low voltage" node. Current does not flow through resistors that connect two "high voltage" nodes or two "low voltage" nodes.
One day, in order to perform circuit maintenance, JOI Corp selected a target resistor and set the states of the nodes such that current did not flow through the target resistor but flowed through all of the other M - 1 resistors. How many ways can you choose a target resistor such that you can set the states of the nodes to allow current to flow through all other resistors but not the target resistor?
Notably, the kinds of inventions that JOI Corp is producing with this mysterious circuit is top secret. No one except for the president of JOI Corp knows what it is for.
Given the details of the electrical circuit, count the number of resistors that can be targeted for maintenance as described above.
Input
Read from standard input.
- On the first line, there are two integers, N and M. This means the electrical circuit contains N nodes and M resistors.
- On the ith line of the next M lines (1 ≤ i ≤ M), there are two integers, Ai and Bi (1 ≤ Ai ≤ N, 1 ≤ Bi ≤ N, Ai ≠ Bi). This means that resistor i connects nodes Ai and Bi.
Output
Print a single integer on a single line to standard output: the number of resistors that can be targeted for maintenance.
Constraints
All test cases satisfy the following constraints:
- 2 ≤ N ≤ 100 000.
- 1 ≤ M ≤ 200 000.
Subtasks
Subtask 1 (10 points):
The following constraints are satisfied:
Subtask 2 (10 points):
- It is possible to reach any node from any other node by following the connections of resistors present in the circuit.
- M = N is satisfied.
Subtask 3 (35 points):
- It is possible to reach any node from any other node by following the connections of resistors present in the circuit.
- M = N + 100 is satisfied.
Subtask 4 (45 points):
No further constraints.
Sample Input 1
4 5
1 2
1 3
1 4
2 4
3 4
Sample Output 1
1
Explanation
In this example, it is possible to prevent current from flowing through resistor 3, for example, by setting nodes 1 and 4 to "high voltage" and nodes 2 and 3 to "low voltage". Since resistor 3 connects nodes 1 and 4, no current will flow through it. However, current will still flow through all other resistors.
Sample Input 2
4 4
1 2
2 3
3 2
4 3
Sample Output 2
2
Explanation
In this example, it is possible to target resistors 1 and 4 for maintenance.
