The Colored Map

Limits: 2 sec., 256 MiB

There are \(N\) cities (numbered from 1 to \(N\)) and \(M\) roads on the map of Ukraine. You want to paint each city in either blue or yellow color. If there is a road between two cities they need to be painted in the same color.

After you pain all the cities you calculate the number \(X\) which is the number of yellow cities on the map. Find the number of different possible values of \(X\) you can get.

Input

The first line contains two integers \(N\) and \(M\) separated with a single space. Each of the following \(M\) lines contains two integers \(A_j\) and \(B_j\) separated with a single space. It means the \(j\)-th road connects cities \(A_j\) and \(B_j\).

Output

The only integer which is the number of different values of \(X\) you can get.

Constraints

\(1 \le N, M \le 100000 (10^5)\),

\(1 \le A_j, B_j \le N\),

\(A_j \ne B_j\).

Samples

Input (stdin) сopy	Output (stdout) сopy
7 7 1 4 4 7 2 5 2 6 5 3 4 1 6 5	4

Notes

The cities 1, 4 and 7 should be painted in the same color. Similarly, the cities 2, 3, 5 and 6 should have the same color. Thus, the number \(X\) can have four different values: 0, 3, 4 or 7.