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 u_i tới máy tính v_i, 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 = p₁, p₂, ..., p_k = t sao cho có đường truyền tin từ máy tính p_i tới máy tính p_i+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 từ file văn bản COMNET.INP

• 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 u_i, v_i.

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ả: Ghi ra file văn bản COMNET.OUT 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.

Ví dụ: