Đường Truyền Tin

Đ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$ máy tính được kết nối bởi $m$ cáp mạng hai chiều. Tìm đường đi ngắn nhất (ít máy tính nhất) từ máy tính $1$ đến máy tính $n$ .

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$ — hai máy tính được nối.

Nếu tồn tại đường đi: in số lượng máy tính trên đường đi, rồi in các máy tính theo thứ tự.
Nếu không có đường đi: in IMPOSSIBLE.

Input	Output	Giải thích
5 5 1 2 1 3 1 4 2 3 5 4	3 1 4 5	Đường ngắn nhất: 1 → 4 → 5, đi qua 3 máy tính.
3 1 1 2	IMPOSSIBLE	Không có đường từ 1 đến 3.

Bình luận

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