Mê cung có phòng đánh số từ đến , được nối với nhau bởi đoạn đường đi chiều nối trực tiếp phòng, đường đi thứ có màu . Giữa phòng có thể có nhiều đường đi nối trực tiếp. Đường đi trực tiếp có thể nối một phòng với chính nó.
Người chơi được máy bay lên thẳng thả xuống phòng và phải tìm đường đi tới phòng . Độ dài của đường đi được tính bằng số đoạn đường nối giữa phòng đã đi qua. Ai có đường đi ngắn nhất sẽ thắng cuộc. Nếu có nhiều người cùng có đường đi ngắn nhất thì so sánh theo thứ tự từ điển các màu đã đi qua. Người có đường đi ngắn nhất với thứ tự từ điển nhỏ nhất sẽ thắng. Đường đi lý tưởng là đường ngắn nhất và có thứ tự từ điển nhỏ nhất.
Yêu cầu: Cho và các đường đi xác định đường màu nối từ phòng tới phòng . Dữ liệu đảm bảo có đường đi từ phòng đến phòng . Hãy xác định đường đi lý tưởng: số đoạn đường và màu của các đoạn đó theo trình tự đi.
Dữ liệu vào:
Dòng đầu tiên chứa hai số nguyên và ;
Dòng thứ trong dòng sau chứa số nguyên và .
Dữ liệu ra:
Dòng đầu tiên chứa số nguyên ;
Dòng thứ hai chứa số nguyên – màu của các đoạn theo trình tự đi.
