Махмуд и Ехаб продолжают свои приключения! Каждый житель Злой Страны знает, что Доктор Зло любит двудольные графы, особенно деревья.
Дерево — это связный граф без циклов. Двудольный граф — это граф, вершины которого можно разбить на 2 множества таким образом, что для любого ребра (u, v) графа вершины u и v лежат в разных множествах. Более формальное определение дерева и двудольного графа дано ниже.
Доктор Зло дал Махмуду и Ехабу дерево, состоящее из n вершин и сказал добавлять рёбра таким образом, чтобы граф оставался двудольным, а также в нём не было петель и кратных рёбер. Какое максимальное число рёбер они могут добавить?
Выходные данные
Выведите одно число — максимальное число рёбер, которые Махмуд и Ехаб могут добавить в граф.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2
1 3
|
0
|
|
2
|
5
1 2
2 3
3 4
4 5
|
2
|