Логіки#10838
Група досконалих логіків знову отримала запрошення стати головними героями нової логічної головоломки. Тепер їм потрібно домовитися, хто з них братиме участь.
Цього разу дія розгортається на неорієнтованому графі з вузлами та ребрами. Кожне ребро з'єднує два різні вузли, і між будь-якими двома вузлами існує не більше одного ребра. Крім того, граф зв'язний, тобто з будь-якого вузла можна дістатися до будь-якого іншого, слідуючи послідовності ребер. У кожному вузлі знаходиться один логік, і кожен логік бачить тільки тих, хто розташований у сусідніх вузлах, з'єднаних з його вузлом ребром.
Логіки підозрюють, що умова задачі пов'язана з кольором їхніх очей, тому вирішують розташуватися так, щоб кожен з них бачив рівно одну людину з блакитними очима. Як завжди, жоден логік не знає кольору своїх власних очей, а отже, навіть логіки з блакитними очима повинні бачити рівно одного блакитноокого.
Яка найменша кількість логіків з блакитними очима необхідна, щоб подібне розташування було можливим?
У першому рядку задано ціле число n~(3 \le n \le 10^5) — кількість вершин графа (і, відповідно, логіків).
У наступних рядках записані пари цілих чисел, що описують ребра графа. Кожне ребро з'єднує два різні вузли, і жодне ребро не зустрічається у вхідних даних двічі.
Якщо вимагане розташування неможливе, виведіть . В іншому випадку виведіть найменшу можливу кількість блакитнооких логіків.
Приклад 1
Приклад 2
Приклад 3