Lan truyền thông báo theo nhóm

Bối cảnh và bài toán

Một nền tảng nội bộ có n nhân sự và m nhóm trao đổi. Nếu hai người cùng xuất hiện trong một nhóm, họ có thể truyền thông báo cho nhau. Việc truyền tiếp tục qua chuỗi quan hệ: một người nhận được tin có thể chuyển cho những người thuộc cùng nhóm với mình, rồi những người đó tiếp tục truyền qua các nhóm khác.

Với mỗi người, hệ thống cần biết nếu thông báo bắt đầu từ người đó thì cuối cùng có bao nhiêu người nhận được.

Yêu cầu

Với mỗi người từ 1 đến n, tính kích thước mạng lan truyền mà người đó thuộc về.

Input

• Dòng 1 chứa n m.
• m dòng tiếp theo mô tả các nhóm. Mỗi dòng bắt đầu bằng k, sau đó là k mã thành viên phân biệt trong nhóm.

Output

In n số nguyên trên một dòng; số thứ i là số người cuối cùng nhận được thông báo nếu bắt đầu từ người i.

Ràng buộc

• 1 <= n, m <= 5 * 10^5
• 0 <= k <= n
• Tổng k của tất cả nhóm không vượt quá 5 * 10^5.

Chấm điểm

Ví dụ 1

Input

7 5
3 2 5 4
0
2 1 2
1 1
2 6 7

Output

4 4 1 4 4 2 2

Giải thích. Các nhóm làm 1,2,4,5 thuộc cùng mạng lan truyền kích thước 4; 3 đứng riêng; 6,7 tạo cụm kích thước 2.

Ví dụ 2

Input

4 2
2 1 2
2 3 4

Output

2 2 2 2

Giải thích. Hai nhóm không giao nhau nên tạo hai component kích thước 2.

Thông tin bài tập

Nguồn: Phỏng theo Educational Codeforces Round 65 – C: News Distribution (2019).