Рассмотрим неориентированный граф с \(N\) вершинами, помеченными \(1\dots N\)
и \(M\) ребрами (\(1\le N\le 2\cdot 10^5, 0\le M\le 4\cdot 10^5\)). Вам дается
двоичная строка \(s_1s_2\dots s_N\). в момент времени \(t\) для каждого
\(t\in [1,N]\),
- Если \(s_t=0\), вершина \(t\) удаляется из графа.
- если \(s_t=1\), вершина \(t\) удаляется из графа и рёбра добавляются
каждой парой соседей вершины \(t\) непосредственно перед удалением.
Заметим, что в обоих случаях, когда вершина удаляется из графа, удаляются
и все связанные с ней рёбра.
Посчитайте количество пар вершин, которые могут достичь друг друга через
некоторую последовательность ребер перед каждым моментом времени \(1\ldots N\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\) и
\(M\).
Вторая строка содержит битовую строку \(s\) длины \(N\).
Каждая из следующих \(M\) строк содержит два целых числа, обозначающих ребро
графа.
ФОРМАТ ВЫВОДА (на экран / stdout):
\(N\) строк, количество пар перед каждым моментом времени.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
111
1 2
1 3
|
3
1
0
|