問題文

本問題は 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$ を出力してください．

サンプル

6 5
1 2 3
1 2
1 3
2 3
1 4
2 5

6

6 5
1 2 3
1 2
1 3
2 3
1 4
1 5

-1

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