問題一覧 > 通常問題

No.1775 Love Triangle 2

レベル : / 実行時間制限 : 1ケース 8.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 9
作問者 : 👑 ygussanyygussany / テスター : 👑 hitonanodehitonanode
4 ProblemId : 7140 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-04 20:33:26

問題文

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

ある学園で,クリスマスに生徒有志でのプレゼント交換会を企画しています. 学園には $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 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$ または $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)$
  • 入力は全て整数である.

出力

$X, Y, Z$ の $3$ 人を含んで,友達どうしが隣り合わないような輪を作るための人数の最小値を出力してください.
ただし,そのような輪が作れない場合には,$-1$ を出力してください.

サンプル

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

生徒 $1, 2, 3$ の間に生徒 $4, 5, 6$ から $1$ 人ずつ挟むことが必要なので,$6$ 人全員が参加しないといけません. 生徒 $1$ と隣り合えるのは生徒 $5, 6$ のみ,生徒 $2$ と隣り合えるのは生徒 $4, 6$ のみであることに注意すると,たとえば $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

生徒 $2$ と隣り合えるのは生徒 $3, 5$ のみ,生徒 $4$ と隣り合えるのは生徒 $6, 8$ のみなので,$7$ 人以上必要です. たとえば $1\ 3\ 2\ 5\ 8\ 4\ 6\ 1$ の順に並んで輪を作れば $7$ 人で達成可能なので,最小値は $7$ となります.

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