Logic#10838
A group of perfect logicians has once again been invited to become the protagonists of a new logical puzzle. This time, they must agree on who among them will participate.
The puzzle takes place on an undirected graph with nodes and edges. Each edge connects two distinct nodes, and there is at most one edge between any pair of nodes. Moreover, the graph is connected, meaning that it is possible to reach any node from any other by following a sequence of edges. Each node hosts one logician, and every logician can see only those who are located in adjacent nodes connected to their own node by an edge.
The logicians suspect that the puzzle has something to do with the color of their eyes. They decide to position themselves so that each of them sees exactly one person with blue eyes. As usual, none of the logicians can see the color of their own eyes — therefore, even the blue-eyed ones must see exactly one blue-eyed person.
What is the minimum number of blue-eyed logicians required to make such an arrangement possible?
The first line contains an integer n~(3 \le n \le 10^5) — the number of vertices in the graph (and, correspondingly, the number of logicians).
The next lines contain pairs of integers describing the edges of the graph. Each edge connects two distinct nodes, and no edge appears more than once in the input.
If the required arrangement is impossible, print . Otherwise, print the minimum possible number of blue-eyed logicians.
Example 1
Example 2
Example 3