Con Đường Dịch Chuyển

Đ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

Trong một trò chơi có $n$ màn chơi và $m$ cổng dịch chuyển một chiều. Bạn bắt đầu ở màn $1$ và cần đến màn $n$ . Hãy tìm một đường đi sử dụng mỗi cổng dịch chuyển đúng một lần. Nếu không thể, in "IMPOSSIBLE".

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$ và $b$ — cổng dịch chuyển từ màn $a$ đến màn $b$ .

Dữ liệu ra

In $m + 1$ số nguyên — các màn chơi theo thứ tự đi qua (bắt đầu tại $1$ , kết thúc tại $n$ ), hoặc in "IMPOSSIBLE".

Ràng buộc

$2 \leq n \leq 10^{5}$
$1 \leq m \leq 2 \times 10^{5}$
Mỗi cặp $(a, b)$ trong dữ liệu vào là duy nhất

Ví dụ

Input	Output	Giải thích
5 6 1 2 1 3 2 4 2 5 3 1 4 2	1 3 1 2 4 2 5	Đường đi sử dụng cả 6 cổng dịch chuyển đúng một lần.
3 2 1 2 2 1	IMPOSSIBLE	Không thể đến màn 3.

Bình luận

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