Chuyến Bay Dài Nhất

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $n$ thành phố và $m$ chuyến bay một chiều tạo thành đồ thị phi chu trình có hướng (DAG). Tìm đường đi dài nhất (nhiều thành phố nhất) từ thành phố $1$ đến thành phố $n$ .

Dữ liệu vào

Dòng 1: hai số nguyên $n$ và $m$ .
$m$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $a$ , $b$ — chuyến bay từ $a$ đến $b$ .

Dữ liệu ra

Nếu không có đường đi: in IMPOSSIBLE.
Nếu có: in số thành phố trên đường đi, rồi in các thành phố theo thứ tự.

Ràng buộc

$2 \leq n \leq 10^{5}$
$1 \leq m \leq 2 \times 10^{5}$

Ví dụ

Input	Output	Giải thích
5 5 1 2 2 5 1 3 3 4 4 5	4 1 3 4 5	Đường 1→3→4→5 dài hơn 1→2→5 (4 so với 3 thành phố).

Bình luận

Không có bình luận tại thời điểm này.