Наконец-то Коровоконг стал правителем мира и теперь может навести в нём порядок. Для начала он хочет, чтобы людям было как можно более удобно путешествовать внутри своих стран.
Представим мир как неориентированный граф из n вершин (городов) и m рёбер (дорог). k из этих вершин являются столицами государств (по одной столице для каждой из k стран).
Любая пара вершин соединена не более чем одним ребром, и никакое ребро не соединяет вершину саму с собой. Более того, для любых двух вершин, являющихся столицами, не существует пути между этими двумя вершинами. Любой граф, удовлетворяющий всем этим условиям, называется стабильным.
Коровоконг хочет добавить в граф как можно больше рёбер, так чтобы он всё ещё оставался стабильным. Выясните, сколько рёбер он может добавить.
Выходные данные
Выведите одно целое число — максимальное количество рёбер, которое Коровоконг может добавить в имеющийся граф, чтобы он остался стабильным.
Примечание
В первом примере граф выглядит следующим образом:
Вершины
1 и
3 являются столицами. Оптимальным решением будет соединить вершину
4 с вершинами
1 и
2. Таким образом, в граф будут добавлены
2 новых ребра. Больше рёбер добавить нельзя, потому что между вершинами
1 и
3 не должно быть пути.
Во втором примере граф выглядит следующим образом:
В него нельзя добавить новые рёбра. Обратите внимание, что нельзя добавлять петли и кратные рёбра.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 1 2
1 3
1 2
|
2
|
|
2
|
3 3 1
2
1 2
1 3
2 3
|
0
|