Cho một đồ thị có hướng gồm ~n~ đỉnh và ~m~ cung, hai con robot đứng ở đỉnh 1 và ~n~. Hãy tìm cách di chuyển nhanh nhất hai con robot đến gặp nhau tại một đỉnh của đồ thị, biết rằng cả hai con robot chỉ được chạy theo các cung định hướng và không được dừng lại cho tới lúc gặp nhau tại một đỉnh nào đó. Thời gian robot đi qua một cung bất kỳ luôn là 1 đơn vị thời gian.

Input:

• Dòng 1: Chứa hai số nguyên dương ~n \leq 1000; m \leq 5000~.
• ~m~ dòng tiếp theo mỗi dòng chứa hai số nguyên ~u, v~ tương ứng với cung ~(u, v)~ của đồ thị.

Output:

• Ghi thời gian tính từ lúc bắt đầu di chuyển đến khi hai robot gặp nhau (nếu không có phương án thì ghi -1).
• Trong trường hợp có phương án thực hiện thì dòng thứ hai ghi hành trình của robot thứ nhất theo thứ tự từ đỉnh 1 đến đỉnh gặp nhau và dòng thứ ba ghi hành trình của robot thứ hai với quy cách tương tự.

Example: