Задача №112877. Polarization
Все знали, что это будет только вопросом времени. Ну и что? Теперь опасность становится с каждым днем все более и более реальной. Сегодня письмо Битарда короля Битотии адресованное Байтазару королю Байтотии, было озвучено на публике. Битотия требует аннексии всей Байтотии, угрожая использовать Битополаризационный Магнит(БПМ). Если БПМ будет использован то каждая дорога в Байтотии станет однонаправленной. Враг хорошо знает, что это будет смертельным ударом по минимализму Байтотской инфраструктуры ведь в Байтотии между каждой парой городов существует единственный путь.
Зафиксировав ориентацию дорог, мы можем посчитать количество пар городов таких, что от одного города из пары можно добраться до другого. Как сильно БМП может испортить Байтотскую инфраструктуру? Посчитайте максимальное и минимальное количество пар таких городов.
Первая строка входных данных содержит целое число N (1 ≤ N ≤ 250000) , количество городов в Байтотии. В следующей n - 1 строке следует описание этих дорог. В каждой строке по 2 целых числа u , v (1 ≤ u , v ≤ n ) , которые указывают, что есть прямая дорога (еще двунаправленная на данный момент) связывающая города с этими номерами.
В первой и единственной строке должно быть напечатано два числа. Первое число должно быть равно минимальному, а второе - максимальному количеству пар городов, которые могли бы оставаться связанным (хотя бы только в одном направлении), после того как дороги будут поляризованы.
Если ваша программа правильно работает при n ≤ 10000 вы получите 60% баллов.
8 1 2 2 3 3 4 4 5 5 6 6 7 7 8
7 28
4 1 2 1 3 1 4
3 5