この問題は、得られる情報を使ってもとのグラフ上で DFS（深さ優先探索）を行うことで解くことができます。

次の \(2\) つのことを考えます。

• 得られる情報だけから DFS を正しく行えること
• \(2N\) 回以下の移動で頂点 \(N\) へ到達できること

1. 得られる情報だけから DFS を行えること

DFS を行うためには「隣接している頂点のうちこれまでに訪れたことがない頂点に移動する（存在しなければこの頂点にはじめに訪れたときの直前にいた頂点に移動する）」ことができればよいです。 隣接している頂点の集合は与えられています。 これまでに訪れた頂点の集合の情報と、直前にいた頂点の情報も（自分が訪れた頂点なので）持っています。

よって、この \(2\) つに共通する頂点へ移動することを繰り返して DFS を行うことができます。 持っている情報から次に進むべき頂点を見つけるのは \(O(N)\) 時間で可能です。\(O(N^2)\) 時間使っても十分高速です。

2. \(2N\) 回以下の移動で頂点 \(N\) へ到達できること

もとのグラフの部分グラフとして、DFS で利用される辺のみからなるグラフを考えます。 すると、このグラフは閉路を持ちません（閉路を持つ場合、すでに訪れたことがある頂点に移動していることになります）。 よって、この部分グラフは特に木になっています。 DFS では連結成分の頂点をすべて訪れ、もとのグラフは連結であったので、この部分グラフは全域木です。

ある頂点から DFS を開始し、他の頂点を探索し終えてもとの頂点に戻ってくるとき、すべての辺を \(2\) 回ずつ通ります。 よって、もとのグラフで頂点 \(1\) から DFS を行って頂点 \(1\) に戻ってくるとき、\(2(N-1)\) 回の移動を行います。 これの途中で頂点 \(N\) に到達しているので、示されました。

実装例は以下のようになります。

#include <bits/extc++.h>

using namespace std;

// 隣接する頂点の情報を受け取る
vector<unsigned> read_vector() {
    unsigned k;
    cin >> k;
    vector<unsigned> ret(k);
    for (auto &&r : ret)
        cin >> r;
    return ret;
}

int main() {
    using namespace std;
    unsigned long N, M;
    cin >> N >> M;

    // dfs を行う関数
    [dfs{[N, visited{vector<unsigned long>(N + 1)}](auto &&f, unsigned now, unsigned prev) mutable -> void {
        // N に到達したら、終了
        if (now == N) {
            string S;
            cin >> S;
            exit(0);
        }

        // 訪れたことを記録
        visited[now] = 1;

        // 隣接している頂点それぞれについて
        for (const auto next : read_vector())
            if (!visited[next]) {
                // 訪れたことがないならそこへ移動
                cout << next << endl;
                f(f, next, now);
            }

        // まわりに未探索の頂点がなくなったら、親に戻る
        cout << prev << endl;
        read_vector();
    }}]() mutable {
        // はじめは頂点 1 から
        dfs(dfs, 1, 1);
    }();
    return 0;
}