Huyện Bụng Bự có thị xã được đánh số từ đến và có con đường một chiều, được đánh số từ đến và con đường thứ nối từ thị xã đến thị xã .
Để ủng hộ đồng bào miền Trung lũ lụt thì có một cuộc thi chạy marathon gây quỹ sẽ được tổ chức trong huyện và sẽ có đội đua (được đánh số từ đến ) sẽ tham gia tranh tài tại cuộc thi này.
Hiện tại ban tổ chức cuộc thi đang phải đối mặt với một vấn đề hết sức khó khăn đó là chọn ra một lộ trình cho cuộc thi này. Ban tổ chức rất mong muốn lộ trình chạy sẽ xuất phát từ một thị xã bất kì, đi qua một số con đường (mỗi con đường chỉ được phép đi duy nhất một lần) và quay lại thị xã xuất phát. Việc này tưởng chừng có vẻ khá đơn giản nhưng lại nảy sinh một vấn đề như sau: Trong ngày diễn ra kì thi, cổ động viên của đội thứ sẽ vây kín xung quanh con đường thứ , và điều này là lợi thế chỉ dành riêng cho đội .
Tất nhiên ban tổ chức vẫn rất muốn rằng việc chọn lộ trình chạy sẽ phải đảm bảo công bằng cho tất cả các thí sinh tham gia. Vì vậy ban tổ chức đã phải có thêm một yêu cầu như sau: Trong lộ trình chạy, không có con đường liên tiếp nào bị vây kín bởi cổ động viên đến từ một đội nào đó (con đường đầu tiên và con đường cuối cùng của lộ trình cũng phải được đảm bảo như vậy). Các bạn hãy giúp ban tổ chức tìm ra lộ trình gồm nhiều đường nhất thỏa mãn hai điều kiện trên nhé!
Dữ liệu vào:
Dòng đầu tiên bao gồm hai số nguyên dương miêu tả số lượng thị xã và số lượng con đường (số lượng đội đua).
dòng tiếp theo, dòng thứ bao gồm ba số miêu tả con đường thứ nối từ thị xã đến thị xã và sẽ bị vây xung quanh bởi cổ động viên của đội .
Dữ liệu ra:
Nếu không tồn tại lộ trình đi hợp lệ, in ra . Ngược lại, dòng đầu tiên in ra số là số lượng con đường trong lộ trình, dòng tiếp theo in ra số là chỉ số của các con đường theo đúng lộ trình đi. Các số phải đôi một phân biệt. Nếu có nhiều lộ trình hợp lệ, in ra một lộ trình bất kì.
