1259 : Game on a Forest

Description

Plover and Georgia are playing a game on a forest graph. Given is an (a forest) with \(n\) nodes and \(m\) edges. Now, Plover and Georgia take turns operating on the graph, with Georgia starting first.

Each operation must be one of the following types:

1. Select an edge in the graph. Then remove it.
2. Select a node in the graph. Then remove both the node and the edges attached to it.

When one of them is unable to operate on his/her turn(which means the graph is empty), the game is lost and the other one wins. Now, assuming that Plover and Georgia are both extremely smart, Georgia wants to know how many different first moves can make her win the game.

Input

The first line contains two integers \(n,m(1\le m<n\le 10^5 )\) , indicating the number of nodes and the number of edges, respectively.

For the next \(m\) lines, the \(i\)-th line contains two integers \(u_i,v_i(1\le u_i<v_i\le n)\), indicating an edge connected the \(u_i\)-th node and the \(v_i\)-th node.

It is guaranteed that for all \(i,j(1\le i<j\le m)\)，\(u_i\ne u_j\) or \(v_i\ne v_j\) is satisfied.

Output

Output contains an integer \(W(0\le W\le n+m)\), indicating the number of different first moves that can make Georgia win.

Sample

3 1
1 2

##CASE##
4 3
1 2
2 3
3 4

2

##CASE##
3

Hint

For the first sample, if Georgia selects node \(1\) or node \(2\) for the first move, she can win the game.

For the second sample, if Georgia selects any one of the \(3\) edges for the first move, she can win the game.

Source

Author

FUDAN