Vòng Trò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

Có $n$ thành phố và $m$ con đường hai chiều. Hãy tìm một vòng tròn — hành trình bắt đầu từ một thành phố, đi qua ít nhất hai thành phố khác, và quay trở lại điểm xuất phát — trong đó tất cả các thành phố trung gian phải khác nhau.

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$ — một con đường.

Dữ liệu ra

Nếu tồn tại vòng tròn: in số lượng thành phố $k$ trên hành trình (thành phố đầu tiên xuất hiện hai lần), rồi in danh sách các thành phố.
Nếu không tồn tại: in IMPOSSIBLE.

Ràng buộc

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

Ví dụ

Input	Output	Giải thích
5 6 1 3 1 2 5 3 1 5 2 4 4 5	4 3 5 1 3	Vòng tròn: 3→5→1→3, qua 3 thành phố phân biệt.
3 2 1 2 2 3	IMPOSSIBLE	Đồ thị là cây — không có chu trình.

Bình luận

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