新規
編集
添付
時間制限:1000ミリ秒
メモリ制限:65536KB
ジョンの旅
Special Judge
問題 
リトル・ジョニーは新しい車を買った。彼は、町をドライブして友達を訪ねてまわることに決めた。ジョニーは彼の友達全員のもとを訪ねたい。しかし彼の友達はとても多い。彼の友達は、各通りにつき1人いる。彼は旅を可能な限り短くすることを考えはじめた。すぐに、それを達成するには各通りを1回ずつ通ればいいことがわかった。当然、彼は旅を、はじめと同じ場所、つまり彼の両親の家で終わりたい。
ジョニーの済む町の通りは1以上n以下(n<1995)の整数で番号づけられている。交差点はそれとは別に、1以上m以下(m<=44)の整数で番号づけられている。どの交差点も44個より多くの通りと繋がっていることはない。町の交差点はそれぞれ違う番号をもっている。各通りはちょうど2つの交差点と繋がっている。同じ番号をもつ通りは存在しない。彼はすぐに、回遊旅行の計画をはじめた。もし1つ以上の回遊旅行の方法があれば、彼はそのうちの1つであり、通りの番号を通る順番で並べた列が辞書順で最も小さいようなものを選ぶ。しかしジョニーは自分の力でそれを見つけることができなかった。
ジョニーを助けるために、前述の最短な回遊旅行を探すプログラムを書け。回遊旅行が存在しない場合は、それに対応したメッセージを出力しなければならない。ジョニーは入力の最初に出現する通りの両端のうち小さいほうの交差点に住んでいるとすること。町の全ての通りは両側通行である。どの通りからも、他の通りに行く道筋が存在する。通りは狭いので、通りの途中で車をUターンさせることはできない。
入力
入力ファイルはいくつかのブロックからなる。各ブロックはそれぞれ1つの町について記述している。ブロックの各行は3つの整数x,y,zが空白を区切りとして書かれている。これは、番号zの通りがあり、交差点xと交差点yを結んでいることを示す。ブロックの終わりは2つの0を含む行によって示される。入力の最後は、空白のブロック、つまり2つの0を含む行によって示される。
出力
それぞれのブロックについて、ジョニーが行くべき回遊旅行のルートを示した、通りの番号の列を含む一行を出力せよ。ただし、そのような回遊旅行のルートが存在しない場合は、「Round trip does not exist.」というメッセージを含む一行を出力せよ。
入力例
1 2 1 2 3 2 3 1 6 1 2 5 2 3 3 3 1 4 0 0 1 2 1 2 3 2 1 3 3 2 4 4 0 0 0 0
出力例
1 2 3 5 4 6 Round trip does not exist.
出典
Central Europe 1995
