This Question: https://codeforces.net/contest/687/problem/A is requiring me to check if the graph is bipartite, but my code https://codeforces.net/contest/687/submission/57552054 is failing on this test case :

10 9

2 5

2 4

2 7

2 9

2 3

2 8

2 6

2 10

2 1

my output:

1

2

9

1 5 4 7 9 3 8 6 10

according to author solution ans is -1 that is graph is not bipartite. Why is the above graph not bipartite? we can clearly divide it into two disjoint set of vertices.

I have another Question: which one is better for bipartition check BFS or DFS? I think DFS is better but not able to Deduce this intuition clearly? can you help me with that. Noobie here, pls go less hard>> :)