問題文

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

サンプル

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

6
1 5 3 4 2 6 1

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
1 3 2 5 8 4 6 1