Задача №114326. Поляризация
Недавно в Байтландии изобрели Битовый Поляризационный Магнит. Если его применить, каждая дорога в Байтландии станет односторонней. Это будет очень плохо, ведь в Байтландии дороги образуют дерево — от каждого города до каждого ровно один путь. В зависимости от того, в какую сторону окажется ориентирована каждая дорога, различные города станут недостижимы друг из друга. Теперь ученые решили выяснить, насколько плохо будет жить в Байтландии, если применить БПМ. Определите минимальное и максимальное количество пар городов, что из первого по прежнему можно будет добраться до другого после применения магнита.
Первая строка содержит число \(n\) — число городов в Байтландии (\(1 \le n \le 250000\)). Следующая \(n - 1\) строка описывают дороги, каждая дорога описывается двумя различными числами от \(1\) до \(n\) — номерами городов, которые он соединяет. От каждого города можно добраться до любого другого.
Выведите два числа: минимальное и максимальное число искомых пар городов.
Подзадача 1 (10 баллов): \(1 \le n \le 15\)
Подзадача 2 (15 баллов): \(1 \le n \le 100\)
Подзадача 3 (15 баллов): \(1 \le n \le 3000\)
Подзадача 4 (10 баллов): \(1 \le n \le 10000\)
Подзадача 5 (35 баллов): \(1 \le n \le 60000\)
Подзадача 6 (15 баллов): Без дополнительных ограничений
4 1 2 1 3 1 4
3 5
8 1 2 2 3 3 4 4 5 5 6 6 7 7 8
7 28