Lộ Trình Phân Biệ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

Có $n$ phòng và $m$ cổng dịch chuyển một chiều. Mỗi ngày, một người chơi bắt đầu từ phòng $1$ và di chuyển đến phòng $n$ , nhưng mỗi cổng dịch chuyển chỉ được dùng tối đa một lần trong toàn bộ trò chơi.

Hãy tìm số lượng người chơi tối đa có thể đi từ phòng $1$ đến phòng $n$ và in ra lộ trình của từng người.

Dữ liệu vào

Dòng đầu gồm 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ừ phòng $a$ đến phòng $b$ .

Dữ liệu ra

Dòng đầu in số $k$ — số lượng người chơi tối đa.

Với mỗi trong $k$ người chơi, in:

Một dòng chứa số phòng trên lộ trình $l$ .
Một dòng chứa $l$ số nguyên — lộ trình từ phòng $1$ đến phòng $n$ .

Ràng buộc

$2 \leq n \leq 500$
$1 \leq m \leq 1000$

Ví dụ

Input	Output	Giải thích
6 7 1 2 1 3 2 6 3 4 3 5 4 6 5 6	2 3 1 2 6 4 1 3 4 6	Có 2 đường đi cạnh-rời nhau: 1→2→6 và 1→3→4→6.
4 2 1 2 3 4	0	Không có đường đi từ 1 đến 4.

Bình luận

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