J. Joyful Jogging
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
A group of people, joyfully jogging. CC BY-SA 4.0 by wal on Pixabay

In the weekend of 26–27 September, the 100 Bruggenloop (100 Bridges Run) takes place in Leiden. In the past few years, the $$$20\,\textrm{km}$$$ route across the 100 bridges has always been the same, but this year, the organization wants to offer more variety.

The city council has already approved a selection of roads to be closed for the race. To maximize the variety, the organization wants to create as many unique courses as the closed roads allow. Each course must form a cycle that starts and ends on the same road and does not reuse any road (it may reuse intersections). Of course, the different courses will have different numbers of bridges, which will contribute to the variety.

To make a course viable, it must include a start zone located on one of its roads. Since each course is a cycle, the start zone also serves as the finish zone. However, installing start zones is expensive, and having fewer of them creates a nicer atmosphere by letting more participants start together.

To support budget planning, determine the minimum number of start zones needed so that every course passes through at least one.

As an example, consider Sample Input 2. Having a single start zone on the edge between vertices $$$7$$$ and $$$8$$$ is not enough, because there is also a cycle along all the outer edges. Placing a second start zone in any of those edges makes sure that every course passes through a start zone.

Visualization of Sample Input 2, where two start zones are needed to cover all courses.
Input

The input consists of:

  • One line with two integers $$$n$$$ and $$$m$$$ ($$$2\leq n \leq {2 \cdot 10^5}$$$, $$$1 \leq m \leq {2 \cdot 10^5}$$$), the number of intersections and the number of roads.
  • $$$m$$$ lines, each with two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$), describing a bidirectional road between intersections $$$u$$$ and $$$v$$$.
It is guaranteed that every intersection is reachable from every other intersection. Note that there might be multiple roads connecting the same pair of intersections.
Output

Output the minimum number of start zones needed to cover all courses.

Examples
Input
4 4
1 2
2 3
3 1
3 4
Output
1
Input
8 9
1 8
8 7
8 2
2 3
3 4
4 7
7 5
5 6
6 1
Output
2