[백준] 자바 문제 풀이 20040 : 골드4

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int[] parent;
	
	public static boolean union(int x, int y) {
		x = find(x);
		y = find(y);
		
		if(x == y) return false;
		
		if(x <= y) parent[y] = x;
		else parent[x] = y;
		return true;
	}
	
	public static int find(int x) {
		if(parent[x] == x) return x;
		return find(parent[x]);
	}

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str = new StringTokenizer(br.readLine(), " ");
		
		int n = Integer.parseInt(str.nextToken());
		int turn = Integer.parseInt(str.nextToken());
		parent = new int[n];
		for(int i = 0; i < n; i++) parent[i] = i;
		
		int f = 0;
		for(int i = 0; i < turn; i++) {
			str = new StringTokenizer(br.readLine(), " ");
			if(!union(Integer.parseInt(str.nextToken()), Integer.parseInt(str.nextToken()))) {
				f = i+1;
				break;
			}
		}
		System.out.println(f);

	}

}