Терористи
Обмеження: 2 сек., 256 МіБ
У руки нашої доблесної міліції потрапила шифрограма, у якій була зашифрована структура підпільної терористичної організації.
Шифрограма була написана на шматку паперу і мала таку структуру: у першому рядку написане одне число, а у всіх наступних – по два. Причому всі числа в шифрограмі, починаючи з другого, не перевищували першого.
Доблесні охоронці закону не розгубилися і зметикували, що перше число в шифрограмі – кількість учасників організації, а в наступних рядках записано, хто з ким підтримує зв’язок (вирішили, що всі учасники організації пронумеровані послідовно, починаючи від одиниці). Проте в голові найрозумнішого співробітника міліції закралася підозра, що ця шифрограма не повна, і в ній не вистачає кількох зв’язків.
Ваше завдання полягає в тому, щоб визначити, скільки саме зв’язків не вистачає на шифрограмі.
Зауважте, що від деяких інформаторів надійшла інформація про те, що задля збереження конфіденційності, структура терористичної організації така, що для будь-яких двох учасників організації існує лише один ланцюжок їхніх колег, через який вони можуть тримати зв’язок.
Вхідні дані
У першому рядку задано одне ціле число \(n\) — кількість терористів.
У наступних рядках задано по два цілих числа через пробіл \(a_i\) \(b_i\).
Ввід закінчується двома нулями через пробіл.
Вихідні дані
У єдиному рядку виведіть одне ціле число — кількість зв’язків, яких не вистачає на шифрограмі.
Обмеження
\(1 \le n \le 10^5\),
\(1 \le a_i, b_i \le n\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
5 1 2 3 4 4 5 0 0 | 1 |
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|