В некоторой социальной сети зарегистрированы \(n\) пользователей. Они общаются между собой в \(m\) группах. Давайте рассмотрим процесс распространения новостей между пользователями.
Изначально какой-нибудь пользователь \(x\) узнает новость из какого-то внешнего источника. Затем этот пользователь отправляет новость всем своим друзьям (два пользователя считаются друзьями, если они оба принадлежат к какой-нибудь группе). Друзья продолжают отправлять новость своим друзьям, и так далее. Процесс заканчивается, когда не останется ни одной пары друзей, в которой один пользователь знает новость, а другой — нет.
Для каждого пользователя \(x\) определите, сколько пользователей в конечном итоге узнает новость, если \(x\) начнет ее распространять.
Выходные данные
Выведите \(n\) целых чисел. \(i\)-е из них должно быть равно количеству пользователей, которые узнают новость, если пользователь \(i\) начнет ее распространять.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 5
3 2 5 4
0
2 1 2
1 1
2 6 7
|
4 4 1 4 4 2 2
|