問題一覧 >
通常問題
No.1776 Love Triangle 2 (Hard)
レベル :
/ 実行時間制限 : 1ケース 10.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ :
/
解いたユーザー数 5
作問者 : 👑
ygussany
/ テスター :
hitonanode
問題文最終更新日: 2021-12-04 18:24:37
問題文
本問題は No.1775 Love Triangle 2 と設定が共通しており,実行時間制限,入力の制約・テストケース,出力形式のみが異なります.
ある学園で,クリスマスに生徒有志でのプレゼント交換会を企画しています.
学園には 人の生徒がおり,各生徒は の出席番号で表されます.
また,生徒 と生徒 は友達どうし であり,それ以外の 人組は友達どうしではありません.
企画代表である の 人は特に仲の良い友達どうしであり,全員で交換会に参加したいと考えています.
また,交換会で新たな交流が生まれるとよいとも考えており,交換会では友達どうしで隣り合わないように参加者全員で つの輪を作るように並んでプレゼント交換を行うことにしました.
望み通りの交換会を開催するためには,最小で何人の参加者が必要でしょうか.
交換会での並び方も併せて求めてください.
出力
行目に「 の 人を含んで,友達どうしが隣り合わないような輪を作るための人数の最小値 」を出力し, 行目に「実際に 人で作ることのできる輪」を「 で始まり で終わる長さ の列」として空白区切りで出力してください.
ただし, 人で作ることのできる輪が複数存在する場合には,出力される列が辞書順で最小となるものを出力してください.
また,そのような輪が作れない場合には, 行目に だけを出力してください.
サンプル
サンプル 1
入力
6 5
1 2 3
1 2
1 3
2 3
1 4
2 5
出力
6
1 5 3 4 2 6 1
生徒 の間に生徒 から 人ずつ挟むことが必要なので, 人全員が参加しないといけません.
生徒 と隣り合えるのは生徒 のみ,生徒 と隣り合えるのは生徒 のみであることに注意すると, の順に並んで輪を作ることができます.
また,これを反転した という輪も条件を満たしますが,辞書順で最小のものを出力する必要があるため不正解となります.
サンプル 2
入力
6 5
1 2 3
1 2
1 3
2 3
1 4
1 5
出力
-1
生徒 と隣り合えるのが生徒 しかおらず,輪を作ることができません.
サンプル 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
生徒 と隣り合えるのは生徒 のみ,生徒 と隣り合えるのは生徒 のみなので, 人以上必要です.
実際出力例の順に並んで輪を作れば 人で達成可能であり,これが作れる輪のうち辞書順で最小のものとなります.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。