問題一覧 > 通常問題

No.1775 Love Triangle 2

レベル : / AI推定難易度 : 3175 / 実行時間制限 : 1ケース 8.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 13
作問者 : ygussany / テスター : 👑 hitonanode
お気に入りにしたユーザー ProblemId : 7140 / 自分の提出
問題文最終更新日: 2021-12-04 20:33:26
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2021 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。