No.1775 Love Triangle 2
タグ : / 解いたユーザー数 13
作問者 :
hitonanode
Problem Statement
This problem shares its setting with No.1776 Love Triangle 2 (Hard); only the time limit, the input constraints and test cases, and the output format differ.
At a certain school, a group of student volunteers is planning a Christmas gift exchange party. The school has $N$ students, each represented by a student number from $1, 2, \dots, N$. Students $A_i$ and $B_i$ are friends with each other $(i = 1, 2, \dots, M)$, and no other pair of $2$ students are friends.
The $3$ organizers $X, Y, Z$ are especially close friends with one another, and they all want to take part in the exchange party. They also hope that the party will lead to new interactions, so they have decided that all participants will stand in $1$ circle to exchange gifts, in such a way that no two friends are adjacent. What is the minimum number of participants required to hold the party as they wish?
Input
$N\ \ M$ $X \ \ Y \ \ Z$ $A_1\ \ B_1$ $A_2\ \ B_2$ $\vdots$ $A_M\ \ B_M$
- $3 \le N \le 100$
- $3 \le M \le \frac{N(N - 1)}{2}$
- $1 \le X < Y < Z \le N$
- $1 \le A_i < B_i \le N \ \ (i = 1, 2, \dots, M)$
- $A_i \neq A_j$ or $B_i \neq B_j \ \ (i \neq j)$
- $(A_1, B_1) = (X, Y),\, (A_2, B_2) = (X, Z),\, (A_3, B_3) = (Y, Z)$
- All input values are integers.
Output
Print the minimum number of people needed to form a circle that includes the $3$ people $X, Y, Z$ and in which no two friends are adjacent.
If no such circle can be formed, print $-1$.
Sample
Sample 1
Input
6 5 1 2 3 1 2 1 3 2 3 1 4 2 5
Output
6
Between students $1, 2, 3$, it is necessary to place students from $4, 5, 6$, $1$ at a time, so all $6$ students must participate. Noting that only students $5, 6$ can be adjacent to student $1$ and only students $4, 6$ can be adjacent to student $2$, a circle can be formed, for example, by standing in the order $1\ 6\ 2\ 4\ 3\ 5\ 1$.
Sample 2
Input
6 5 1 2 3 1 2 1 3 2 3 1 4 1 5
Output
-1
The only student who can be adjacent to student $1$ is student $6$, so a circle cannot be formed.
Sample 3
Input
8 12 1 2 4 1 2 1 4 2 4 2 6 2 7 2 8 3 4 3 6 4 5 4 7 5 6 5 7
Output
7
Only students $3, 5$ can be adjacent to student $2$, and only students $6, 8$ can be adjacent to student $4$, so at least $7$ people are necessary. For example, forming a circle in the order $1\ 3\ 2\ 5\ 8\ 4\ 6\ 1$ achieves this with $7$ people, so the minimum is $7$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。