Đuổi Bắt Cảnh Sá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

Tên cướp đang ở ngã tư $1$ (ngân hàng) và cần chạy trốn đến ngã tư $n$ (cảng). Cảnh sát muốn chặn tối thiểu số con đường để ngăn tên cướp đến đích. Hãy tìm số con đường tối thiểu cần chặn và liệt kê các con đường đó.

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 hai chiều giữa $a$ và $b$ .

Dữ liệu ra

Dòng 1: số nguyên $k$ — số con đường cần chặn.
$k$ dòng tiếp theo: mỗi dòng gồm hai số nguyên — hai đầu của con đường bị chặn.

Ràng buộc

$2 \leq n \leq 500$
$1 \leq m \leq 1000$
Không có cạnh đa

Ví dụ

Input	Output	Giải thích
4 5 1 2 1 3 2 3 3 4 1 4	2 3 4 1 4	Chặn hai đường 3-4 và 1-4 là đủ để ngăn đường từ 1 đến 4.

Bình luận

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