410320: GYM104009 D Bipartite
Description
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.
InputThe 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$$$).
OutputOn 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.
ExampleInput3 3 1 3 1 2 2 3Output
2