사이클을 만드는 간선

첫 줄에 노드의 개수 n (1 이상 100000 이하) 과 간선의 개수 m (0 이상 4000 이하) 이 주어집니다. 이어서 m개의 줄에 간선 a b 가 주어진 순서대로 그래프에 추가됩니다.

간선을 하나씩 추가하다가 처음으로 사이클이 생기는 간선의 번호(1번부터)를 출력하세요. 끝까지 사이클이 생기지 않으면 0 을 출력합니다.

예시

입력

3 3
1 2
2 3
1 3

출력

3