410320: GYM104009 D Bipartite

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Bipartitetime limit per test2 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

You are given an undirected graph with $$$N$$$ nodes and a list of edges of size $$$M$$$. You are asked to partition the given list of edges into minimum number of contiguous and disjoint subsequences such that every subsequence describes a bipartite graph. Please note, the graphs formed by different subsequences are completely independent.

Input

The first line of the input contains the integers $$$N$$$ ($$$2 \leq N \leq 200000$$$) and $$$M$$$ ($$$1 \leq M \leq 200000$$$), denoting the number of nodes and the size of the edge list.

Each of the following $$$M$$$ lines contains $$$2$$$ positive integers, denoting an edge between nodes $$$x$$$ and $$$y$$$ ($$$1 \leq x, y \leq N, x \neq y$$$).

Output

On a single line, print the minimum number of subsequences to partition the given list of edges such that every graph inside a subsequence is bipartite.

ExampleInput
3 3
1 3
1 2
2 3
Output
2

加入题单

上一题 下一题 算法标签: