10308: CF EDU - DSU - Step 2 - J. First Non-Bipartite Edge
Description
A bipartite graph is such an undirected graph that it is possible to split its vertices in two parts in such a way, that edges connect vertices from different parts only.
In this problem, $m$ edges are added one by one to initially empty graph with $n$ vertices. Your task is to determine the index of the first edge such that the graph is not bipartite after its addition.
An empty graph of $n$ vertices is a graph containing $n$ vertices and no edges.
Input
The first line contains two integers $n,m\ (1 ≤n,m≤ 3·10^5)$ — the number of vertices and the number of added edges.
The next $m$ lines contain information about $m$ edges as pairs of integers $a_i,b_i\ (1 ≤a_i,b_i≤n)$. The graph does not contain multiple edges and loops at any moment of time.
Output
Sample 1 Input
3 3
1 2
2 3
1 3
Sample 1 Output
3
Sample 2 Input
4 5
1 2
2 3
3 4
1 4
2 4
Sample 2 Output
5