{"code":"cses2130","name":"CSES - Distinct Routes II | Lộ trình phân biệt II","description":"Một trò chơi bao gồm $n$ phòng và $m$ cổng dịch chuyển tức thời. Vào đầu mỗi ngày, bạn bắt đầu ở phòng $1$ và bạn phải đến phòng $n$.\r\n\r\nBạn có thể sử dụng tối đa mỗi cổng dịch chuyển tức thời một lần trong trò chơi. Bạn muốn chơi trò chơi trong chính xác $k$ ngày. Mỗi khi bạn sử dụng bất kỳ cổng dịch chuyển tức thời nào, bạn phải trả một đồng xu. Số đồng xu tối thiểu bạn phải trả trong $k$ ngày nếu bạn chơi tối ưu là bao nhiêu?\r\n\r\n#### Input\r\n\r\n- Dòng đầu vào đầu tiên có ba số nguyên $n$, $m$ và $k$: số lượng phòng, số lượng cổng dịch chuyển tức thời và số ngày bạn chơi trò chơi. Các phòng được đánh số $1, 2, \\ldots, n$.\r\n- Sau này, có $m$ dòng mô tả các cổng dịch chuyển tức thời. Mỗi dòng có hai số nguyên $a$ và $b$: có một cổng dịch chuyển tức thời từ phòng $a$ đến phòng $b$.\r\n- Không có hai cổng dịch chuyển tức thời có phòng bắt đầu và kết thúc giống nhau.\r\n\r\n#### Output\r\n\r\n- Đầu tiên in một số nguyên: số đồng xu tối thiểu bạn phải trả nếu bạn chơi tối ưu. Sau đó, in $k$ mô tả lộ trình theo ví dụ. Bạn có thể in bất kỳ giải pháp hợp lệ nào. \r\n- Nếu không thể chơi trò chơi trong $k$ ngày, chỉ in $-1$.\r\n\r\n#### Constraints\r\n\r\n- $2 \\leq n \\leq 500$\r\n- $1 \\leq m \\leq 1000$\r\n- $1 \\leq k \\leq n - 1$\r\n- $1 \\leq a, b \\leq n$\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        8 10 2\r\n        1 2\r\n        1 3\r\n        2 5\r\n        2 4\r\n        3 5\r\n        3 6\r\n        4 8\r\n        5 8\r\n        6 7\r\n        7 8\r\n        ```\r\n\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        6\r\n        4\r\n        1 2 4 8\r\n        4\r\n        1 3 5 8\r\n        ```","points":2500.0,"partial":true,"time_limit":1.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}