Logičari
레이팅 미적용의견: 0
A group of perfect logicians has again received a request to be the main protagonists
of a new logic puzzle. They must now agree upon which \(n\) of them should participate.
This time the logic puzzle takes place on an undirected graph with \(n\) nodes, and
logically, \(n\) edges. Each edge connects two different nodes and between any two
nodes there is at most one edge. Additionally, the graph is connected, which means
that it is possible to go from any node to any other node via a sequence of edges.
For each node there will be one logician located on that node and each logician is
able to see precisely those logicians whose nodes are connected by an edge with their
own node.
They already suspected that the catch might be related to their eye color, so they decided to arrange
themselves so that each logician sees exactly one other person with blue eyes. As it ususally happens
to be, none of the logicians can see their own eye color, which means that even logicians with blue eyes
should see exactly one other person with blue eyes.
What is the least number of bl\(ue-ey\)ed logicians needed to make the required arrangement?
Subtask 1 (10 points): Each logician sees exactly two other logicians.
Subtask 2 (10 points): \(3 \le n \le 20\)
Subtask 3 (40 points): \(3 \le n \le 1000\)
Subtask 4 (50 points): \(3 \le n \le 100\,000\)
The first line contains the integer \(n - th\)e number of nodes in the graph, and also the number of logicians.
The following \(n\) lines contain pairs of integers representing the edges of the graph. Each edge connects
two different nodes and no edge is repeated twice in the input.
If the required arrangement does not exist, in the first and only line outp\(ut -1\).
Otherwise, in the first and only line output the required least number of bl\(ue-ey\)ed logicians.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 10점 | Each logician sees exactly two other logicians. |
2 | 10점 | \(3 \le n \le 20\) |
3 | 40점 | \(3 \le n \le 1000\) |
4 | 50점 | \(3 \le n \le 100\,000\) |
4
1 2
2 3
3 4
4 123
1 2
2 3
3 1-17
1 2
2 3
3 4
4 5
5 6
6 7
2 44Clarification of the first example:
Blue-eyed logicians could for example be those on nodes 1 and 2.
Clarification of the second example:
If only one of the logicians has blue eyes, then he surely can’t see anyone else with blue eyes. If there are
two or more of them with blue eyes, then surely someone will see more than one person with blue eyes.
평가 및 의견
Logičari
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Logičari