{"code":"cjpaysballas","name":"CJ thanh toán BALLAS","description":"Khu vực *SAN ANDREAS* có $N$ ngôi nhà và $M$ đường giao thông **một chiều**. Mỗi con đường kết nối trực tiếp giữa 2 ngôi nhà. Các ngôi nhà được đánh số từ $1$ tới $N$. *CJ* đang chuẩn bị thanh toán nhóm *BALLAS* ở một ngôi nhà trong khu vực, và sẽ bắt đầu tại nhà của *CJ*. Nhà của *CJ* có chỉ số là $s$, nhà của nhóm *BALLAS* có chỉ số là $t$. Một đường đi gọi là đường đi đơn nếu trong quá trình đi từ nhà *CJ* tới nhà của nhóm *BALLAS*, tất cả ngôi nhà đi qua nhiều nhất một lần. Và tồn tại ít nhất một đường đi từ $s$ tới $t$  (vì thế *CJ* mới có thể đi thanh toán được).\r\n\r\nHãy tìm cho *CJ* đường đi đơn **ngắn nhất** để *CJ* nhanh chóng thanh toán nhóm *BALLAS* càng nhanh càng tốt (*CJ* còn nhiều việc chưa giải quyết xong). Nếu có nhiều đường đi đơn ngắn nhất, thì chỉ ra đường đi có **thứ tự từ điển nhỏ nhất** trong số đó.\r\n#### Input\r\n- Dòng đầu tiên chứa 4 số nguyên dương $N,M,s,t \\ (1 \\leq s, t \\leq N, s \\ne t)$.\r\n- $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $u, v \\ (1 \\leq u, v \\leq N, u \\ne v)$ thể hiện có đường đi một chiều nối từ ngôi nhà $u$ tới ngôi nhà $v$ trong khu vực.\r\n\r\n#### Output \r\n- Ghi ra trên một dòng các ngôi nhà theo đúng thứ tự trên đường đi ngắn nhất tìm được, bắt đầu từ ngôi nhà $s$, kết thúc ở ngôi nhà $t$ theo thứ tự từ điển nhỏ nhất (Ví dụ $10$ có thứ tự từ điển lớn hơn $5$, $5$ có thứ tự từ điển lớn hơn $1$).\r\n\r\n#### Scoring \r\n- Subtask $1$ ($30\\%$ số điểm): $N \\leq 10^3, M \\leq 10^4$.\r\n- Subtask $2$ ($70\\%$ số điểm): $N \\leq 10^5, M \\leq 10^6$.\r\n\r\n#### Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        8 12 1 8\r\n        1 3\r\n        3 5\r\n        7 6\r\n        1 2\r\n        2 4\r\n        2 3\r\n        3 1\r\n        3 7\r\n        6 8\r\n        4 6\r\n        6 2\r\n        7 8 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        1 3 7 8\r\n        ```\r\n    ??? warning \"Note\"\r\n        ![](https://i.imgur.com/ooEONv8.png)","points":200.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"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}}