Охоронці#4028
Королівські замки в одному стародавньому королівстві побудовані за дизайном короля Сейна, першого з його династії, який правив за принципом "розділяй і володарюй". Усі замки мають ієрархічну структуру, що складається з взаємопов'язаних будівель. Кожна будівля містить зали та коридори, які їх з'єднують.
Спочатку замок складається лише з однієї будівлі (головної будівлі). Коли населення зростає, замок розширюється: додається нова периферійна будівля, яка приєднується до однієї з існуючих будівель. Як і будь-яка інша будівля, нова будівля також складається з залів і коридорів. Додатковий коридор з'єднує зал в існуючій будівлі з залом у новій будівлі. Цей коридор є єдиним шляхом доступу до нової будівлі.
Кількість залів у будівлі не перевищує .
Рисунок 1: План замку з прикладу, наведеного нижче.
У часи неспокою король контролює всі коридори, стратегічно розміщуючи охоронців у залах. Він просить вас визначити мінімальну кількість охоронців, необхідних для контролю всіх коридорів у замку (оскільки він хоче зберегти свою особисту охорону якомога більшою). Зверніть увагу, що після останньої пожежі в замку немає дверей, тому ми можемо безпечно припустити, що охоронець, розміщений у залі, може контролювати всі з'єднані коридори.
Вхід містить кілька описів замків. У межах замку кожен зал ідентифікується унікальним номером від до . Кожен замок рекурсивно визначається, починаючи з опису головної будівлі:
Рядок, що містить три цілі числа, які представляють кількість залів у цій будівлі (2 \leq n \leq 10), кількість коридорів у цій будівлі (1 \leq m \leq 45) та кількість периферійних будівель, які пізніше були приєднані до цієї будівлі (0 \leq w \leq 10).
Для кожного з коридорів:
Рядок, що містить два цілі числа (кожне \leq 10\,000), які представляють два зали, з'єднані цим коридором. Обидва зали розташовані всередині поточної будівлі.
Для кожної з периферійних будівель:
Рядок, що містить два цілі числа, які описують коридор, що веде до цієї периферійної будівлі. Перше число представляє зал у поточній будівлі, а друге число представляє зал у периферійній будівлі.
Структура периферійної будівлі та будь-яких новіших будівель, які пізніше були приєднані до неї, описана повторенням правил до .
Замок повністю з'єднаний: будь-який зал безпосередньо або опосередковано досяжний з будь-якого іншого залу. Коридори з однаковим початковим і кінцевим залом не існують, і для кожних двох залів існує не більше одного коридору між ними.
Для кожного замку виведіть один рядок, що містить додатне ціле число: мінімальну кількість охоронців, яких потрібно розмістити в залах, щоб усі коридори в замку були під контролем.
Приклад 1