Trong một tu viện Nhật Bản, nổi tiếng với lối sống nhịn ăn và khổ hạnh nghiêm túc, người đứng đầu bộ phận đấu vật sumo đã quyết định tổ chức các cuộc thi huấn luyện cho võ sĩ ~N~ của mình. Anh ta xác định trình tự chính xác của ~M~ trận đấu và những người tham gia (hai võ sĩ đối mặt với nhau trong mỗi trận đấu).

Chỉ vài phút trước cuộc thi, Người đứng đầu nhận ra rằng mình có thể dễ dàng khuấy động mọi thứ lên một chút! Anh ta có thể chia các chiến binh của mình thành hai đội để chỉ những chiến binh của các đội khác nhau đối đầu với nhau trong mỗi trận chiến. Vì lịch chiến đấu đã được lập sẵn và nó không đáp ứng được điều kiện này, đồng thời chúng ta không được thay đổi nó vì bất kỳ lý do chính đáng nào, nên Người đứng đầu chỉ còn một lựa chọn. Đó là chia các đấu sĩ thành hai đội để các đấu sĩ của cùng một đội đối đầu với nhau trong trận đấu càng muộn càng tốt.

Giúp người đứng đầu! Với một lịch thi đấu nhất định, hãy xác định số thứ tự của trận đấu đầu tiên trong đó hai đấu sĩ của cùng một đội phải đối mặt với nhau, với điều kiện là chúng ta chia họ theo cách tốt nhất có thể để trận đấu bắt buộc diễn ra càng muộn càng tốt khả thi. Trong tất cả dữ liệu thử nghiệm, cuộc chiến như vậy chắc chắn sẽ xảy ra.

Input

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 \le N \le 100 000)~, số lượng đấu ngư. Các máy bay chiến đấu được đánh dấu bằng số từ ~1~ đến ~N~.
• Dòng đầu vào thứ hai chứa số nguyên ~M~ ~(1 \le M \le 300 000)~, số trận đánh.
• Mỗi dòng trong số ~M~ dòng tiếp theo chứa các trận đánh theo thứ tự chúng phải diễn ra. Mỗi dòng chứa hai số nguyên khác nhau trong khoảng ~[1, N]~: nhãn của các võ sĩ sẽ đối đầu với nhau.

Output

• Dòng đầu tiên và duy nhất xuất ra phải chứa số thứ tự (từ ~1~ đến ~M~) của trận đấu được yêu cầu

Sample Input 1

5
5
1 2
2 3
3 4
4 5
5 1

Sample Output 1

5

Sample Input 2

6
8
1 2
3 4
5 6
1 3
1 6
4 5
2 4
2 6

Sample Output 2

6