Задача F. PartyHard
У соцiальнiй мережi Kilogram користувачi мають можливiсть створювати двостороннi дружнi зв’язки з iншими користувачами. Соцiальна мережа поки що молода, тому функцiї розриву зв’язкiв там поки що немає.
Що там ще є, так це поняття груп користувачiв. Два користувачi A i B належать до однiєї групи, якщо знайдеться деяка послiдовнiсть користувачiв a1, a2, ..., ak така, що користувач A є другом користувача a1, користувач a1 є другом користувача a2 (загалом, користувач ai є другом користувача ai+1), а користувач ak є другом користувача B.
Коли усi користувачi однiєї групи знають одне одного напряму (тобто попарно дружать), група перетворюється на супергрупу. Адмiнiстрацiя Kilogram бажає знати кiлькiсть супергруп пiсля кожного утворення нової пари друзiв. Допоможiть їм!
Технiчнi умови
Програма PartyHard читає з першого рядка два числа N i M(2 ≤N≤ 105,1 ≤M≤ 
- кiлькiсть користувачiв i кiлькiсть створених дружнiх зв’язкiв. Далi йдуть M пар чисел 1 ≤aibi≤ N - користувачi, що стають друзями.
Програма виводить рiвно M чисел - кiлькiсть супергруп користувачiв пiсля кожного створення нової пари друзiв.
Приклади
|
Введення |
Виведення |
|
5 3 1 5 5 4 4 1 |
4 2 3 |