Видобуток Вашого Бізнесу#2288
Джон Диггер — власник великої копальні ілудієвого фосдексу. Копальня складається з серії тунелів, які з'єднуються у різних великих розв'язках. На відміну від деяких власників, Диггер турбується про добробут своїх працівників і непокоїться щодо планування копальні. Зокрема, його хвилює, що може існувати така розв'язка, обвалення якої призведе до того, що працівники в одній частині копальні будуть відрізані від інших (ілудієвий фосдекс, як вам відомо, надзвичайно нестабільний). Щоб цього уникнути, він хоче обладнати спеціальні аварійні шахти для виходу з розв'язок на поверхню. Він міг би встановити аварійну шахту на кожній розв'язці, але Диггер не настільки переймається своїми працівниками. Замість цього він хоче встановити мінімальну кількість аварійних шахт так, щоб якщо будь-яка розв'язка обвалиться, усі працівники, які пережили обвал, мали шлях на поверхню.
Напишіть програму, яка підраховує мінімальну кількість аварійних шахт і загальну кількість способів їх розміщення.
Вхідні дані складаються з кількох тестових випадків. Перша стрічка кожного випадку містить додатне ціле число (N \leq 5 \cdot 10^4), що вказує кількість тунелів у копальні. Далі йдуть стрічок, кожна з яких містить по два різних цілих числа і , де та — номери розв'язок. Розв'язки нумеруються підряд, починаючи з . Кожна пара розв'язок з'єднана не більше ніж одним тунелем. Кожна система тунелів утворює одну зв'язну одиницю (тобто з однієї розв'язки можна дістатися до будь-якої іншої).
Після останнього тестового випадку йде стрічка, що містить нуль.
Для кожного тестового випадку виведіть його номер, потім мінімальну кількість необхідних аварійних шахт у системі тунелів та загальну кількість способів їх розташування. Можна вважати, що результат поміщається у знакове -бітне ціле число.
Дотримуйтесь формату, показаного у зразку виводу.
Приклад 1