Anton has invented a new team sport called waterball (similar to paintball, but with water). He wants to share his invention with his $$$n$$$ friends. Anton has good relationships with all his friends, but it's not guaranteed that his friends have the same relationships with each other. Specifically, we know that friend number $$$a_i$$$ conflicts with friend $$$b_i$$$.
Anton was given a list of $$$m$$$ conflicting pairs ($$$a_i;b_i$$$). Now, it seems like it would be possible to divide the players into two teams, but it's not that simple for Anton...
He wants to divide these $$$m$$$ conflicting pairs into segments in such a way that:
For example, let's say we have an array of conflicting pairs $$$[(1, 2), (2, 3), (1, 3)]$$$. We can take the first two pairs in the first segment. In this case, we can form the teams: $$$[1, 3]$$$ and $$$[2]$$$. In the second segment, we can take the last pair. $$$1$$$ and $$$3$$$ must be in different teams, and $$$2$$$ can be in either team. Alternatively, we can assign the first pair to the first segment, and the last two to the second segment. Note that we cannot assign the first and third pairs to the same segment, and the second pair to another. This is because a segment should only contain consecutive pairs. We also cannot assign all pairs to the same segment, as there would always be a team where people conflict.
Anton has made the statement complicated again, and now he can't solve the problem. Help him by telling him the minimum number of segments into which he can divide the pairs to satisfy the above conditions.
The first line contains two integers $$$n$$$, $$$m$$$ ($$$1 \le n, m \le 10^6$$$) — the number of friends and the number of conflicting relationships among friends.
The next $$$m$$$ lines contain two integers each, $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \neq b_i$$$), indicating that friend $$$a_i$$$ conflicts with friend $$$b_i$$$.
It is guaranteed that no pair ($$$a;b$$$) is repeated more than once.
Print a single integer — the answer to the problem.
3 31 22 31 3
2
5 102 41 23 41 31 54 52 33 51 42 5
3
The first example is explained in the legend above.
In the second example, for instance, it is possible to divide into the following segments: $$$[1;6]$$$, $$$[7;9]$$$, $$$[10;10]$$$.
In the first segment, the teams can be formed as $$$[1,4]$$$, $$$[2,3,5]$$$ — $$$1$$$ and $$$4$$$ do not conflict with each other, as well as the pairs $$$(2;3)$$$, $$$(2;5)$$$, $$$(3;5)$$$.
In the second segment, the teams can be formed as $$$[1,3]$$$, $$$[2,4,5]$$$ — $$$1$$$ and $$$3$$$ do not conflict with each other, as well as the pairs $$$(2;4)$$$, $$$(2;5)$$$, $$$(4;5)$$$.
In the third segment, the teams can be formed as $$$[1,2]$$$, $$$[3,4,5]$$$ — $$$1$$$ and $$$2$$$ do not conflict with each other, as well as the pairs $$$(3;4)$$$, $$$(3;5)$$$, $$$(4;5)$$$.