This problem can be solved by performing DFS (Depth-First Search) on the hidden graph using the information revealed.

We explain the following two facts:

• One can perform DFS only based on the given clues.
• One can reach vertex \(N\) with at most \(2N\) moves.

1. One can perform DFS only based on the given clues.

In order to do the DFS, it is sufficient to be capable of “moving to an adjacent unvisited vertex” (or if there is no such vertex, go back to the last vertex before visiting the current for the first time). The set of adjacent vertices are given. We also know the set of visited vertex and the last vertex visited (because they are where we have visited).

Therefore, based on these information, one can perform DFS on this graph. You can find the next vertex to advance based on what you know in an \(O(N)\) time. Spending \(O(N^2)\) time is fast enough.

2. One can reach vertex \(N\) with at most \(2N\) moves.

Consider the subgraph of the original graph, consisting only of the edges used in the DFS. Then, this graph does not have a closed path (if so, it means that you advance to a visited vertex). Therefore, this subgraph is especially a tree. The DFS visits all the vertices in the connected component, and the original graph is connected, so this subgraph is a spanning tree.

If you start a DFS from a vertex, visit all other vertices and go back to the original vertex, you visit every vertex twice. Thus, if you start DFS from vertex \(1\) on the original graph and go back to vertex \(1\), you repeat \(2(N-1)\) moves. You always reach vertex \(N\) in the course of this, it is proved.

The following is a sample code.

#include <bits/extc++.h>

using namespace std;

// Read adjacent vertices
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;

    // Performs DFS
    [dfs{[N, visited{vector<unsigned long>(N + 1)}](auto &&f, unsigned now, unsigned prev) mutable -> void {
        // If you reach N, terminate
        if (now == N) {
            string S;
            cin >> S;
            exit(0);
        }

        // Record that you visited this vertex
        visited[now] = 1;

        // For each adjacent vertex,
        for (const auto next : read_vector())
            if (!visited[next]) {
                // go there if it is unvisited
                cout << next << endl;
                f(f, next, now);
            }

        // If there is no more adjacent unvisited vertices, go back to the parent
        cout << prev << endl;
        read_vector();
    }}]() mutable {
        // Start from vertex 1
        dfs(dfs, 1, 1);
    }();
    return 0;
}