Одна острівна держава вирішила побудувати мережу мостів між островами. По кожному мосту можна переміщуватись в обидві сторони.
Був розроблений план черговості будівництва мостів і відомо, що після будівництва усіх мостів можна буде проїхати з будь-якого острова, на будь-який інший (можливо через деякі проміжні острови).

Але цей момент може настати раніше, ніж будуть побудовані усі мости. Вам необхідно визначити, після побудови якого моста вже можна буде потрапити з будь-якого острова, на будь-який інший.

Формат вхідних даних

Перший рядок містить два числа: кількість островів \(N\) (\(1 \le N \le 10000\)) і кількість мостів \(M\) (\(1 \le M \le 50000\)).
Далі йдуть \(M\) рядків, кожен з яких містить два числа \(X\) та \(Y\) (\(1 \le X,Y \le N\)) - номера островів, які має з'єднати черговий міст.

Формат вихідних даних

Програма має вивести єдине число - номер моста, після побудови якого можна буде дістатись з будь-якого острова, на будь-який інший

Приклад вхідних даних

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

Приклад вихідних даних

4