Kết nối bóng đèn

Nam vừa mua một dàn đèn để trang trí trong nhà vào những ngày lễ. Khi mua, Nam nhận được \(n\) bóng đèn, \(m\) sợi dây và một bản hướng dẫn sử dụng.

Bản hướng dẫn có \(m\) dòng, mỗi dòng gồm hai số nguyên \(x\) và \(y\) \((x \neq y)\), cho biết rằng bước này sẽ sử dụng một sợi dây để kết nối hai bóng \(x\) và \(y\).

Nam không hoàn toàn tin tưởng vào bản hướng dẫn này, nên muốn kiểm tra xem liệu sau khi thực hiện đến bước thứ \(i\), dàn đèn có được hoàn thành hay không. Một dàn đèn được coi là hoàn thành khi có thể truyền điện từ bóng đèn số \(1\) đến tất cả các bóng còn lại thông qua các sợi dây nối.

Nhiệm vụ của bạn là xác định số thứ tự \(i\) của bước cuối cùng cần thiết để hoàn thành dàn đèn. Nếu không thể hoàn thành dàn đèn, hãy in ra FAILURE.

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((1 \leq n, m \leq 10^5)\) --- số bóng đèn và số sợi dây.

\(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x\) và \(y\) \((1 \leq x, y \leq n, x \neq y)\) --- cho biết bóng \(x\) và bóng \(y\) được nối với nhau.

Output

Nếu có thể hoàn thành dàn đèn, in ra một số nguyên \(i\) --- số thứ tự của bước cuối cùng để hoàn thành dàn đèn.

Ngược lại, in ra FAILURE.

Example

4 6
1 2
2 3
3 1
1 4
4 2
2 4

4

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

FAILURE