Hành Tinh và Vương Quốc

Đ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$ hành tinh và $m$ cổng dịch chuyển một chiều. Hai hành tinh thuộc cùng một vương quốc nếu có đường đi từ $a$ đến $b$ và từ $b$ đến $a$ . Hãy xác định mỗi hành tinh thuộc vương quốc nào.

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$ — cổng dịch chuyển một chiều từ $a$ đến $b$ .

Dữ liệu ra

Dòng 1: số nguyên $k$ — số vương quốc.
Dòng 2: $n$ số nguyên — nhãn vương quốc của mỗi hành tinh (từ 1 đến $k$ ).

Ràng buộc

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

Ví dụ

Input	Output	Giải thích
5 6 1 2 2 3 3 1 3 4 4 5 5 4	2 1 1 1 2 2	Hành tinh 1,2,3 tạo thành một vương quốc; 4,5 tạo thành vương quốc khác.

Bình luận

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