package algorithm.baek.graph;

import algorithm.TestCase;

import java.io.*;

import java.text.ParseException;

import java.util.StringTokenizer;

/**

* https://www.acmicpc.net/problem/20040

* 사이클 게임

*/

public class CycleGame implements TestCase {

static int[] parent;

@Override

public void test() throws ParseException, IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

StringTokenizer st = new StringTokenizer(br.readLine());

int n = Integer.parseInt(st.nextToken());

int m = Integer.parseInt(st.nextToken());

init(n);

int result = 0;

for (int i = 1; i <= m; i++) {

st = new StringTokenizer(br.readLine());

int a = Integer.parseInt(st.nextToken());

int b = Integer.parseInt(st.nextToken());

if (isSameParent(a, b)) {

result = i;

break;

}

union(a, b);

}

bw.write(result + "\n");

bw.flush();

bw.close();

}

public void init(int n) {

parent = new int[n];

for (int i = 0; i < n; i++) {

parent[i] = i;

}

}

public void union(int a, int b) {

int pa = find(a);

int pb = find(b);

if (pa < pb) {

parent[pb] = pa;

} else {

parent[pa] = pb;

}

}

public int find(int a) {

if (parent[a] == a) {

return a;

}

return parent[a] = find(parent[a]);

}

public boolean isSameParent(int a, int b) {

return find(a) == find(b);

}

}