В некоторой социальной сети зарегистрированы \(n\) пользователей. Они общаются между собой в \(m\) группах. Давайте рассмотрим процесс распространения новостей между пользователями.
Изначально какой-нибудь пользователь \(x\) узнает новость из какого-то внешнего источника. Затем этот пользователь отправляет новость всем своим друзьям (два пользователя считаются друзьями, если они оба принадлежат к какой-нибудь группе). Друзья продолжают отправлять новость своим друзьям, и так далее. Процесс заканчивается, когда не останется ни одной пары друзей, в которой один пользователь знает новость, а другой — нет.
Для каждого пользователя \(x\) определите, сколько пользователей в конечном итоге узнает новость, если \(x\) начнет ее распространять.
В первой строке записаны два целых числа \(n\) и \(m\) (\(1 \le n, m \le 5 \cdot 10^5\)) — the количество пользователей и групп, соответственно.
Затем следуют \(m\) строк, каждая из которых описывает группу. \(i\)-я строка начинается целым числом \(k_i\) (\(0 \le k_i \le n\)) — количество пользователей в \(i\)-й группе. Затем следуют \(k_i\) различных чисел, обозначающих пользователей, принадлежащих к \(i\)-й группе.
Гарантируется, что \(\sum \limits_{i = 1}^{m} k_i \le 5 \cdot 10^5\).
Выведите \(n\) целых чисел. \(i\)-е из них должно быть равно количеству пользователей, которые узнают новость, если пользователь \(i\) начнет ее распространять.
7 5 3 2 5 4 0 2 1 2 1 1 2 6 7
4 4 1 4 4 2 2
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач