Дан неориентированный связный граф G из n вершин и n ребер. G не содержит петель и кратных ребер. Пусть у каждого ребра этого графа есть два состояния: включено и выключено. Изначально все ребра выключены.
Также вам даны m запросов вида (v, u) — изменить состояние всех ребер на кратчайшем пути из вершины v в вершину u в графе G, если таких путей несколько, выбирается лексикографически наименьший. Более формально, рассмотрим все кратчайшие пути из вершины v в вершину u как последовательности вершин v, v1, v2, ..., u. Среди таких последовательностей выбирается лексикографически наименьшая.
Требуется после каждого запроса сказать, сколько компонент связности в графе, вершины которого совпадают с вершинами графа G, а ребра совпадают с включенными ребрами графа G.
Выходные данные
Выведите m строк по одному целому числу в каждой — ответы на запросы.
Примечание
Рассмотрим первый пример. Будем синим выделять на рисунке включенные ребра.
-
Граф до применения операций. В графе нет включенных ребер, поэтому 5 компонент связности есть изначально.
-
Граф после запроса v = 5, u = 4. Видно, что в графе 3 компоненты, если рассматривать только включенные ребра.
-
Граф после запроса v = 1, u = 5. Видно, что в графе 3 компоненты, если рассматривать только включенные ребра.
Лексикографическое сравнение двух последовательностей одинаковой длины (k чисел) происходит следующим образом. Последовательность x лексикографически меньше последовательности y если существует такое i (1 ≤ i ≤ k), что xi < yi, а для любого j (1 ≤ j < i) xj = yj.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
2 1
4 3
2 4
2 5
4 1
5 4
1 5
|
3
3
|
|
2
|
6 2
4 6
4 3
1 2
6 5
1 5
1 4
2 5
2 6
|
4
3
|