Do you know the company Just Odd Inventions? The business of this company is to create "just odd inventions." Here, we will refer to it as the JOI company.

In a certain laboratory of the JOI company, there is a complex electrical circuit. The circuit consists of $N$ nodes and $M$ thin electrical resistors. The nodes are numbered from $1$ to $N$. Each node can be set to either a "high voltage" or "low voltage" state. Each electrical resistor connects two nodes, and current flows when one of these nodes is in a "high voltage" state and the other is in a "low voltage" state. No current flows through an electrical resistor connecting two "high voltage" nodes or two "low voltage" nodes.

One day, for the maintenance of this circuit, the JOI company decided to choose one electrical resistor such that no current flows through only that resistor, while current flows through the remaining $M-1$ resistors, by setting the voltage of each node. To satisfy this condition, how many electrical resistors can be chosen as the one through which no current flows?

Note that what kind of inventions the JOI company is making using this strange circuit is top secret within the company, and no one except the president knows.

Task

Given the information about the circuit, write a program to calculate the number of electrical resistors that can be chosen as the one through which no current flows during maintenance.

Input

Read the following data from standard input:

• The first line contains two space-separated integers $N$ and $M$, representing that there are $N$ nodes and $M$ electrical resistors.
• The $i$-th line of the following $M$ lines ($1 \le i \le M$) contains two space-separated integers $A_i$ and $B_i$ ($1 \le A_i \le N, 1 \le B_i \le N, A_i \neq B_i$), representing that the $i$-th electrical resistor connects node $A_i$ and node $B_i$.

Output

Output the number of electrical resistors that can be chosen as the one through which no current flows during maintenance in a single line.

Constraints

All input data satisfies the following conditions:

• $2 \le N \le 100\,000$.
• $1 \le M \le 200\,000$.

Subtasks

Subtask 1 [10 points]

The following conditions are satisfied:

• $N \le 1\,000$.
• $M \le 2\,000$.

Subtask 2 [10 points]

• It is possible to reach any node from any other node by following some number of connected electrical resistors.
• $M = N$ is satisfied.

Subtask 3 [35 points]

• It is possible to reach any node from any other node by following some number of connected electrical resistors.
• $M \le N + 100$ is satisfied.

Subtask 4 [45 points]

There are no additional constraints.

Examples

Input 1

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

Output 1

1

Note 1

In this example, it is possible to ensure that current does not flow only through the 3rd electrical resistor. For example, one can set node 1 and node 4 to "high voltage," and node 2 and node 3 to "low voltage." Since the 3rd electrical resistor connects node 1 and node 4, no current flows through the 3rd electrical resistor.

It is not possible to choose any resistor other than the 3rd one as the one through which no current flows during maintenance.

Input 2

4 4
1 2
2 3
3 2
4 3

Output 2

2

Note 2

In this example, the 1st electrical resistor or the 4th electrical resistor can be chosen as the one through which no current flows during maintenance.

Input 3

13 16
1 6
2 6
3 1
3 2
4 7
4 7
5 9
6 5
8 2
8 13
9 11
10 3
11 10
11 12
12 8
13 6

Output 3

3

Figure 1. Example 1 circuit diagram