Euler: Circuit / Path / None

Euler: give the verdict (assume connected)

Read a connected undirected graph and print the Euler verdict:

• 0 odd-degree vertices → an Euler circuit exists, print 2;
• 2 odd-degree vertices → an Euler path exists, print 1;
• otherwise (4, 6, ...) → neither, print 0.

Complete it: count odd-degree vertices, then print 2 / 1 / 0 by the rule above.

Pitfall (straight from the bug lab): don't accept only "all even" — 0 odd is a circuit, but 2 odd also counts (a path); missing it misjudges a drawable graph as not. This task assumes the graph is connected, so the odd count alone decides.

Input

• Line 1: V E (connected).
• Next E lines: u v, undirected edge.

Output

• One line: 2 (circuit) / 1 (path) / 0 (neither).

Example: input 4 4 / 0 1 / 1 2 / 2 3 / 3 0 -> 2 (a square, all degree 2, 0 odd -> Euler circuit).