問題一覧 > 通常問題

No.1776 Love Triangle 2 (Hard)

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 3
作問者 : 👑 ygussanyygussany / テスター : 👑 hitonanodehitonanode
1 ProblemId : 7123 / 自分の提出
問題文最終更新日: 2021-12-04 18:24:37

問題文

本問題は No.1775 Love Triangle 2 と設定が共通しており,実行時間制限,入力の制約・テストケース,出力形式のみが異なります.

ある学園で,クリスマスに生徒有志でのプレゼント交換会を企画しています. 学園には $N$ 人の生徒がおり,各生徒は $1, 2, \dots, N$ の出席番号で表されます. また,生徒 $A_i$ と生徒 $B_i$ は友達どうし $(i = 1, 2, \dots, M)$ であり,それ以外の $2$ 人組は友達どうしではありません.

企画代表である $X, Y, Z$ の $3$ 人は特に仲の良い友達どうしであり,全員で交換会に参加したいと考えています. また,交換会で新たな交流が生まれるとよいとも考えており,交換会では友達どうしで隣り合わないように参加者全員で $1$ つの輪を作るように並んでプレゼント交換を行うことにしました. 望み通りの交換会を開催するためには,最小で何人の参加者が必要でしょうか. 交換会での並び方も併せて求めてください.

入力

$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$ または $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)$
  • 入力は全て整数である.

出力

$1$ 行目に「 $X, Y, Z$ の $3$ 人を含んで,友達どうしが隣り合わないような輪を作るための人数の最小値 $k$ 」を出力し,$2$ 行目に「実際に $k$ 人で作ることのできる輪」を「 $X$ で始まり $X$ で終わる長さ $k + 1$ の列」として空白区切りで出力してください. ただし,$k$ 人で作ることのできる輪が複数存在する場合には,出力される列が辞書順で最小となるものを出力してください.
また,そのような輪が作れない場合には,$1$ 行目に $-1$ だけを出力してください.

サンプル

サンプル 1
入力
6 5
1 2 3
1 2
1 3
2 3
1 4
2 5
出力
6
1 5 3 4 2 6 1

生徒 $1, 2, 3$ の間に生徒 $4, 5, 6$ から $1$ 人ずつ挟むことが必要なので,$6$ 人全員が参加しないといけません. 生徒 $1$ と隣り合えるのは生徒 $5, 6$ のみ,生徒 $2$ と隣り合えるのは生徒 $4, 6$ のみであることに注意すると,$1\ 5\ 3\ 4\ 2\ 6\ 1$ の順に並んで輪を作ることができます. また,これを反転した $1\ 6\ 2\ 4\ 3\ 5\ 1$ という輪も条件を満たしますが,辞書順で最小のものを出力する必要があるため不正解となります.

サンプル 2
入力
6 5
1 2 3
1 2
1 3
2 3
1 4
1 5
出力
-1

生徒 $1$ と隣り合えるのが生徒 $6$ しかおらず,輪を作ることができません.

サンプル 3
入力
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
出力
7
1 3 2 5 8 4 6 1

生徒 $2$ と隣り合えるのは生徒 $3, 5$ のみ,生徒 $4$ と隣り合えるのは生徒 $6, 8$ のみなので,$7$ 人以上必要です. 実際出力例の順に並んで輪を作れば $7$ 人で達成可能であり,これが作れる輪のうち辞書順で最小のものとなります.

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