Xây Dựng Đường

Đ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ố, ban đầu không có đường nối. Mỗi ngày, một tuyến đường mới được xây dựng nối hai thành phố. Sau mỗi ngày, hãy cho biết: số lượng thành phần liên thông và kích thước thành phần lớn nhất.

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$ — tuyến đường xây dựng ngày đó.

Dữ liệu ra

In $m$ dòng, mỗi dòng gồm hai số nguyên: số thành phần liên thông và kích thước thành phần lớn nhất sau ngày tương ứng.

Ràng buộc

$1 \leq n \leq 10^{5}$
$1 \leq m \leq 2 \times 10^{5}$
$1 \leq a, b \leq n$ , $a \neq b$

Ví dụ

Input	Output	Giải thích
5 3 1 2 1 3 4 5	4 2 3 3 2 3	Ngày 1: {1,2},{3},{4},{5} — 4 thành phần, lớn nhất 2. Ngày 2: {1,2,3},{4},{5} — 3 thành phần, lớn nhất 3. Ngày 3: {1,2,3},{4,5} — 2 thành phần, lớn nhất 3.

Bình luận

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