問題一覧 > 通常問題

No.1776 Love Triangle 2 (Hard)

レベル : / AI推定難易度 : 3375 / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 7
作問者 : ygussany / テスター : 👑 hitonanode
お気に入りにしたユーザー ProblemId : 7123 / 自分の提出
問題文最終更新日: 2021-12-04 18:24:37
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

Problem Statement

This problem shares its setting with No.1775 Love Triangle 2; only the time limit, the input constraints and test cases, and the output format differ.

At a certain school, student volunteers are planning a Christmas gift exchange party. The school has $N$ students, each represented by a student number $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 with each other.

The $3$ organizers $X, Y, Z$ are especially close friends with one another, and all of them want to take part in the exchange party. They also hope that the party will create new connections, so they have decided that all participants will line up to form $1$ circle such that no two friends are adjacent and exchange gifts in it. What is the minimum number of participants required to hold the party they want? Also find an arrangement for the party.

Input

$N\ \ M$
$X \ \ Y \ \ Z$
$A_1\ \ B_1$
$A_2\ \ B_2$
   $\vdots$
$A_M\ \ B_M$

  • $3 \le N \le 150$
  • $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 inputs are integers.

Output

On line $1$, output "the minimum number $k$ of people needed to form a circle that includes the $3$ people $X, Y, Z$ and in which no two friends are adjacent". On line $2$, output "a circle that can actually be formed with $k$ people" as "a sequence of length $k + 1$ that starts with $X$ and ends with $X$", separated by spaces. If there are multiple circles that can be formed with $k$ people, output the one for which the output sequence is lexicographically smallest.
If no such circle can be formed, output only $-1$ on line $1$.

Sample

Sample 1
Input
6 5
1 2 3
1 2
1 3
2 3
1 4
2 5
Output
6
1 5 3 4 2 6 1

Between students $1, 2, 3$, it is necessary to place $1$ student each from students $4, 5, 6$, 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 by lining up in the order $1\ 5\ 3\ 4\ 2\ 6\ 1$. The reversed circle $1\ 6\ 2\ 4\ 3\ 5\ 1$ also satisfies the conditions, but it is judged as incorrect because the lexicographically smallest one must be output.

Sample 2
Input
6 5
1 2 3
1 2
1 3
2 3
1 4
1 5
Output
-1

Only student $6$ can be adjacent to student $1$, 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
1 3 2 5 8 4 6 1

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 required. In fact, forming a circle in the order of the sample output achieves this with $7$ people, and it is the lexicographically smallest circle that can be formed.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。