Giao Thư

Đ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$ ngã tư và $m$ con đường hai chiều. Bưu điện đặt tại ngã tư số $1$ . Hãy tìm một tuyến đường bắt đầu và kết thúc tại ngã tư $1$ , đi qua mỗi con đường đúng một lần. Nếu không tồn tại tuyến đường như vậy, 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$ — con đường giữa ngã tư $a$ và $b$ .

Dữ liệu ra

In các ngã tư theo thứ tự đi qua (bắt đầu và kết thúc tại $1$ ), hoặc in "IMPOSSIBLE".

Ràng buộc

$2 \leq n \leq 10^{5}$
$1 \leq m \leq 2 \times 10^{5}$
Không có cạnh đa và cạnh tự vòng

Ví dụ

Input	Output	Giải thích
6 8 1 2 1 3 2 3 2 4 2 6 3 5 3 6 4 5	1 2 6 3 2 4 5 3 1	Tuyến đường đi qua tất cả 8 con đường đúng một lần.
3 2 1 2 2 3	IMPOSSIBLE	Ngã tư 1 và 3 có bậc lẻ → không tồn tại chu trình Euler.

Bình luận

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