English text is not available in this practice contest.
ICPC 市では毎年7月に,ICPC City Parade Ceremony が開かれる.このお祭りでは多くの屋台が ICPC 市の路上に出店され,多くの市民が屋台を楽しんで巡る.あなたはこのお祭りを効率よく巡りたいと考えた.
ICPC 市は,1 から N までの番号のついた N か所の交差点と,M 本の通りからなる.それぞれの通りは異なる 2 つの交差点を繋ぎ,双方向に通行可能である.複数の通りが同じ交差点の組を直接繋ぐことはない.どの 2 つの交差点についても,いくつかの通りを経由することで,互いに行き来することができる.
お祭りでは,屋台がすべての通りに出店される.お祭りを最大限楽しむためには,全ての屋台を巡るべきである.また,各屋台を何度も見物するのは飽きてしまうため,同じ屋台を 3 回以上通るのは避けたい.更に,同じ通りを連続で行き来するのは,見物したばかりの屋台を通ることになるので遠慮したい.つまり,同じ通りを 2 回通る場合には,間に別の通りを 1 つ以上挟むようにしたい.
果たしてその様な順路が存在するのかと気になったあなたは,ICPC 市の地図を元に,どの交差点の順番で通るべきか解析するプログラムを書くことにした.
ここで,順路とは,任意の交差点から始まり,今いる交差点から延びる通りを一つ選んで別の交差点へ移動することを繰り返し,任意の交差点で終わるものを指す.始めと終わりの交差点は,同じであっても,違っていてもよい.また,ある通りを移動している途中で,元いた交差点へ引き返してはならない.
入力は 50 個以下のデータセットからなる.各データセットは次の形式で表される.
N M a1 b1 ... aM bM
1 行目には,市の交差点の数を表す整数 N と,通りの数を表す整数 M が空白区切りで与えられる. 続く M 行には, それぞれ空白で区切られた 1 以上 N 以下の相異なる整数 ai と bi が与えられ,これは i 番目の通りが交差点 ai と交差点 bi を繋いでいる事を表す.ここで,2 つ以上の通りが同じ交差点の組を直接繋ぐことはないことが保証される. N は 2 以上 20,000 以下,M は 1 以上 20,000 以下であることが保証される. 入力の終わりは空白区切りのゼロふたつの行で示す.
各データセットに対し,問題文中の条件を満たす順路が存在するならば,順路上の交差点番号を順番に,空白区切りで一行に出力せよ.答えとしてあり得るものが複数ある場合は,どれを出力しても正解となる.もしもそのような順路が存在しないならば,代わりに -1 を一行に出力せよ.
なお,出力検証機の都合上,改行コードには LF または CR+LF のいずれかを使用せよ.他の問題と異なり,CR のみを使用した場合は誤答扱いとなる.
6 9 1 2 2 3 3 4 4 5 5 6 1 6 1 4 2 5 3 6 5 4 1 2 1 3 1 4 1 5 10 19 1 7 6 8 3 8 2 3 7 9 6 9 3 9 4 9 1 6 8 9 9 10 7 10 4 5 3 4 6 10 6 7 1 9 5 8 2 9 0 0
1 2 3 4 5 6 1 4 5 2 1 6 3 -1 4 9 6 10 9 2 3 8 9 1 6 10 7 1 9 3 4 5 8 6 7 9