Cánh đồng cỏ (Grass Cownoisseur)

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.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$ trường và $M$ con đường một chiều. Bắt đầu và kết thúc tại trường $1$ , Bessie muốn thăm nhiều trường khác nhau nhất có thể. Cô được phép đi ngược một cạnh duy nhất trong suốt hành trình (tức là đi từ $v$ đến $u$ trên cạnh $u \to v$ một lần).

Tìm số trường tối đa có thể thăm (kể cả trường $1$ ).

Dữ liệu vào

Dòng đầu chứa $N$ và $M$ .

$M$ dòng tiếp theo, mỗi dòng hai số nguyên $u$ , $v$ : con đường một chiều từ $u$ đến $v$ .

Dữ liệu ra

Số nguyên là số trường tối đa.

Ràng buộc

$1 \leq N, M \leq 10^{5}$
Tất cả các cạnh đều khác nhau

Ví dụ

Input	Output	Giải thích
7 10 1 2 3 1 2 5 2 4 3 7 3 5 3 6 6 5 7 2 4 7	6	Đi 1→2→4→7→(đảo ngược 3→7, tức đi 7→3)→3→1. Thăm được: 1,2,3,4,7 và có thêm 6 nếu đường đi qua 6. Đáp án là 6.
20 48 8 16 7 4 6 19 14 9 17 13 17 3 14 18 20 17 20 10 5 9 5 18 5 4 7 1 7 19 17 8 6 13 8 3 11 14 12 15 17 16 6 7 17 10 1 3 1 13 6 2 10 13 2 7 19 1 14 12 6 20 2 9 1 8 2 1 18 15 5 11 18 12 1 17 20 8 1 10 6 16 6 1 14 15 1 20 1 16 11 5 2 19 1 5 20 3	9	—

Bình luận

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