Công ty X lên kế hoạch kết nối n máy tính đang hoạt động trong công ty. Các máy tính được đánh số từ 1 đến n. Theo kế hoạch Công ty lắp đặt m đường truyền tin một chiều để kết nối các máy tính. Các đường truyền tin được đánh số từ 1 tới m. Đường truyền tin thứ i cho phép truyền tin từ máy tính ui tới máy tính vi, i = 1,2, ...,m. Các đường truyền tin sẽ được lắp đặt lần lượt theo thứ tự từ 1 tới m. Việc lắp đặt một đường truyền tin mất đúng 1 đơn vị thời gian.
Ta nói máy tính s có thể truyền tin tới máy tính t nếu tồn tại một dãy các máy tính s = p1, p2, ..., pk = t sao cho có đường truyền tin từ máy tính pi tới máy tính pi+1, i = 1, 2, ...,k-1. Trong quá trình lắp đặt, đến một thời điểm nào đó máy tính 1 có thể truyền tin đến máy tính n theo những đường truyền tin đã được lắp đặt.
Yêu cầu: Giả sử việc lắp đặt các đường truyền tin được thực hiện liên tục bắt đầu từ thời điểm 0, hãy tính thời điểm sớm nhất mà máy tính 1 có thể truyền tin tới máy tính n.
Dữ liệu vào:
- Dòng thứ nhất chứa hai số nguyên dương n, m (2 ≤ n ≤ 300000; 1 ≤ m ≤ 500000);
- Dòng thứ i trong số m dòng tiếp theo chứa hai số nguyên dương ui, vi.
- Hai số liên tiếp trên một dòng được ghi cách nhau ít nhất một dấu cách.
Kết quả ra:
- Một số nguyên duy nhất là thời điểm sớm nhất mà máy tính 1 có thể truyền tin tới máy tính n.
- Trong trường hợp đã lắp đặt xong m đường truyền tin mà máy tính 1 vẫn không thể truyền tin tới máy tính n, ghi ra file kết quả một số -1.