Railway Tour

Time limit1sMemory limit512 MB

Summary
Given an undirected graph, find the minimum number of edge-disjoint trails needed to cover every edge exactly once.
Level

Medium6 of 10

Topics
Graph, DFS, Math, Implementation
Solved
No attempts yet

Problem

Korea has N cities C1, C2, ..., CN, connected by M bidirectional railway lines between pairs of cities.

Gahee, who loves railways, wants to go on railway tours. A railway tour is a journey from a starting city to an ending city that uses only railway lines, without riding any single railway line more than once. The starting city and the ending city may be the same, and a city may be visited multiple times.

Gahee wants to ride every railway line exactly once using the minimum number of railway tours. Determine how many railway tours she must take.

Input

The first line of input gives two integers N (1 ≤ N ≤ 200,000) and M (1 ≤ M ≤ 300,000).

Each of the following M lines gives two distinct integers u, v (1 ≤ u, v ≤ N). This means a bidirectional railway line exists between Cu and Cv.

At most one railway line directly connects any pair of cities.

Output

Output the minimum number of railway tours Gahee must take.

Examples4

  1. Example 1

    Input
    11 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
3 9
9 10
10 11
    Expected output
    2

  2. Example 2

    Input
    3 3
1 2
2 3
3 1
    Expected output
    1

  3. Example 3

    Input
    5 2
1 2
3 4
    Expected output
    2

  4. Example 4

    Input
    5 10
1 2
2 3
3 4
4 5
5 1
1 3
2 4
3 5
4 1
5 2
    Expected output
    1