410320: GYM104009 D Bipartite

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.

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$$$).

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.

3 3
1 3
1 2
2 3

2