問題一覧 > 通常問題

No.1776 Love Triangle 2 (Hard)

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

問題文

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

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

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

入力

N  M
X  Y  Z
A1  B1
A2  B2
   
AM  BM

  • 3N150
  • 3MN(N1)2
  • 1X<Y<ZN
  • 1Ai<BiN  (i=1,2,,M)
  • AiAj または BiBj  (ij)
  • (A1,B1)=(X,Y),(A2,B2)=(X,Z),(A3,B3)=(Y,Z)
  • 入力は全て整数である.

出力

1 行目に「 X,Y,Z3 人を含んで,友達どうしが隣り合わないような輪を作るための人数の最小値 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もしくは右上の雲マークをクリックしてアカウントを作成してください。