CF1167C News Distribution

Statement

There are n users communicating in m groups. Two users are friends if they belong to at least one common group. News starting from user x is repeatedly sent to all friends. For every user, find how many users eventually know the news.

Input

The first line contains n,m (1 <= n,m <= 500000). Each of the next m lines contains k_i followed by k_i distinct user indices. The sum of all k_i does not exceed 500000.

Output

Print n integers. The i-th integer is the number of users reached when user i starts distributing the news.

Example

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

4 4 1 4 4 2 2