Тридевятое царство состоит из $$$N$$$ городов, соединенных $$$N-1$$$ дорогой таким образом, что от каждого города можно доехать до любого другого города, двигаясь только по дорогам.
Организаторы чемпионата по программированию «Тридесятый кубок» решили провести очный тур чемпионата на площадках в нескольких городах царства.
При этом они хотят гарантировать, что расстояние от любого города царства до ближайшей площадки проведения не превышает двух дорог. То есть для любого города должно выполняться хотя бы одно из условий:
- Либо в самом городе есть площадка проведения;
- Либо в одном из соседних городов есть площадка;
- Либо в одном из соседних к одному из соседних городов есть площадка.
В то же время в целях экономии организаторы стремятся минимизировать количество площадок. Вам, как лучшему игроку царства в пошаговые стратегии, предстоит помочь организаторам найти данное количество.
Первая строка содержит целое число $$$N$$$ $$$(2 \le n \le 100)$$$ — количество городов в царстве.
В каждой из следующих $$$N-1$$$ строк содержатся по два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le N$$$) — номера городов, между которыми проложена одна из дорог царства.
Гарантируется, что от любого города можно добраться до любого другого города, двигаясь только по описанным дорогам.
Выведите единственное целое число — минимальное число городов, выбранных для проведения очного тура чемпионата, чтобы для каждого города выполнялось хотя бы одно из условий:
- Либо в самом городе есть площадка проведения;
- Либо в одном из соседних городов есть площадка;
- Либо в одном из соседних к одному из соседних городов есть площадка.
8 6 5 2 1 8 7 2 3 3 4 1 5 5 7
2
Тестовый пример
Для проведения чемпионата:
- одну из площадок можно разместить в городах $$$2$$$, $$$3$$$ или $$$4$$$;
- другую площадку можно разместить в одном из городов $$$5$$$ или $$$7$$$.
Например, один из вариантов размещения — пара городов $$$4$$$ и $$$5$$$. В таком случае ближайшая площадка расположена:
- Город $$$1$$$: в соседнем городе $$$5$$$;
- Город $$$2$$$: в городе $$$4$$$, являющемся соседним к соседнему городу $$$3$$$;
- Город $$$3$$$: в соседнем городе $$$4$$$;
- Город $$$4$$$: в самом городе;
- Город $$$5$$$: в самом городе;
- Город $$$6$$$: в соседнем городе $$$5$$$;
- Город $$$7$$$: в соседнем городе $$$5$$$;
- Город $$$8$$$: в городе $$$5$$$, являющемся соседним к соседнему городу $$$7$$$.
