This page is still under construction.

Parts of this page are still being built. What you see may change.

Toll

Time limit1sMemory limit128 MB

Summary
Each selected town must charge on exactly one incident road, and no road may be charged by both endpoints. Maximize selected towns in a general graph, not necessarily the whole graph.
Level

Hard9 of 10

Topics
Graph, Math
Solved
No attempts yet

Problem

The kingdom of Byteotia has nn towns joined by mm two-way roads. Every road directly connects two different towns, and no pair of towns is joined by more than one road (a road may still run through a tunnel or over a flyover).

Each town would like to collect a toll from travellers, but to keep the merchants happy the king restricts this privilege with two rules:

  • A town that collects toll does so on exactly one of the roads that touch it, no matter which way a traveller uses that road.
  • On any single road at most one of its two endpoint towns may collect toll; the two endpoints can never both charge the same road.

Because of these rules some towns can be left with no road to charge. Your task is to find the largest number of towns that can collect toll at the same time.

Write a program that:

  • reads the description of Byteotia's road network from standard input,
  • computes the maximum number of towns that can collect toll,
  • writes that number to standard output.

Input

The first line contains two integers nn and mm (1≤n≤1000001 \le n \le 100000, 1≤m≤2000001 \le m \le 200000): the number of towns and the number of roads. Towns are numbered from 11 to nn. Each of the next mm lines contains two integers aia_i and bib_i (1≤ai<bi≤n1 \le a_i < b_i \le n), meaning that towns aia_i and bib_i are directly connected by a road.

Output

Print one integer: the maximum number of towns that can collect toll while obeying the rules above.

Hint

In the picture an arrow points from a road to the town that collects toll on it. Every town is served by exactly one road, and no road is charged by both of its endpoints; the road between towns 11 and 22 collects no toll at all. In this network all four towns manage to collect toll, so the answer is 44.

Examples1

  1. Example 1

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