Please refer to this question.
What would be your answer for
N=5 M=6
1 2
2 3
3 4
4 5
5 1
1 4
My answer is 2.
But according to this submission that passed all test cases, the answer is 0.
Am I going wrong somewhere ?
Or are the test cases weak ?
The test cases are not weak, infact it’s very weak. All the cases have 0 answer. See this
solution .
I wont call it weak, i will call that broken to be honest.
In sample input, he is removing edges from trees (trees have no cycle in first place), and here the answer of ALL the test cases is 0? WTF?
yupp…exactly 
This is ridiculous!
Does anyone have an elegant solution that can be proved to be correct?
the question was a bit unclear for me. Can you just tell me, how the cycle is defined in 2nd sample case ??
There is no odd cycle in the second case, and removing any edge will not give you an odd cycle, thus, you can remove all edges.
This just tells us in a case where no odd cycle exists, all edges are removable.
For what cases will the answer be zero, except for M=0?
Here’s what I got:
If there exists a segment such that it connects with all odd cycles and such that removing this segment will result in all cycles become even, then the answer will not be zero.
For me, the problem reduces down to finding this one segment if it exists, but I’m sure I’m overdoing it.
If you want the cases where the answer will be zero:
The first case can be reduced to searching for the common edges in which all odd cycles have, and those edges are basically the answer to the problem. Searching for common edges feels like an intense algorithm. Is there an elegant solution for it?
To answer @liaojh
If you use c++ or java (idk about other languages), testing all 2*10^4 edges actually works. Basically just remove every edge and do a bfs to see if the graph will be 2-colorable.
Original author:
https://www.codechef.com/viewsolution/14667767 which passes in 0.03s
My java solution:
https://www.codechef.com/viewsolution/14687222 which passes in 0.15s
It may not be “elegant”, but it is definitely simple. Or most likely, the test cases are weak.
Wow, now that I think about it, this N^2 = 4 \times 10^8 brute force actually does fit within bounds.
Thanks a lot bro!! 
Oh wow, I used the same approach but with DFS and got TLE.
I guess there should be a test for setting test cases !
Because its really disheartening to see this after putting a lot of effort into the question 
It may be because dfs requires a lot of function calling, but in the solutions above an array was used as a queue for bfs which could be faster.