#1512 · Chuyến bay dài nhất

Vừa qua, sinh viên Khoa Công nghệ thông tin Trường Đại học Công nghệ TP.HCM (HUTECH) đã tham gia tranh tài tại cuộc thi Olympic Tin học Sinh viên Việt Nam lần thứ 32 diễn ra tại Huế. Với nền tảng kiến thức vững chắc cùng bản lĩnh tự tin, các đội thi HUTECH đã xuất sắc gặt hái được nhiều thành tích đáng nể.

Sau khi đạt giải trong kì thi lập trình Olympic Tin học sinh viên, ban giám hiệu trường HUTECH quyết định tặng cho đội tuyển Olympic một chuyến bay miễn phí đến thành phố S, chuyến bay có thể đi qua một hoặc nhiều thành phố. Tất nhiên, mọi người trong đội đều muốn đi qua nhiều thành phố nhất có thể. Bạn hãy giúp đội tuyển chọn ra đường bay cho chuyển đi này nhé.

• Dòng đầu tiên gồm hai số n và m: số lượng các thành phố và số lượng các chuyến bay. Các thành phố được đánh số từ 1 đến n, trong đó TP. HCM là 1 và thành phố S là n.
• m dòng tiếp theo là các chuyến bay, mỗi chuyến bao gồm hai số a và b: có chuyến bay một chiều từ thành phố a đến thành phố b.

• Dòng đầu tiên là số thành phố tối đa mà đội tuyển có thể đi qua.
• Dòng thứ hai là tuyến đường mà đội sử dụng

Lưu ý: Nếu không có đường nào để đến được thành phố S từ TP. HCM thì hãy in ra -1.