#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
#define INF 987654321
using namespace std;
void bfs(int src, vector<vector<int> >& graph, vector<int>& parent){
    int N = graph.size();
    vector<int> visit = vector<int>(N, 0);
    parent= vector<int>(N, -1);
    queue<int> q;
    visit[src] = 1;
    parent[src] = src;
    q.push(src);
    while (!q.empty()){
        src = q.front();
        q.pop();
        for (int i = 0; i < N; i++){
            if (graph[src][i] == 1 && !visit[i]){
                visit[i] = 1;
                parent[i] = src;
                q.push(i);
            }
        }
    }
}

vector<int> solve(int v, const vector<int>& parent){
    vector<int> mang(1000000, 0);
    if (v == -1){ return mang; }
    vector<int> path(1, v);
    while (parent[v] != v){
        v = parent[v];
        if (v == -1){ return mang; }
        path.push_back(v);
    }
    reverse(path.begin(), path.end());
    return path;
}
int main(){
    double C;
    cin >> C;
    while (C--){
        int N, M;
        cin >> N >> M;
        vector<vector<int > > graph;
        for (int i = 0; i < N; i++){ 
            vector<int> vbuf;
            for (int j = 0; j < N; j++){
                vbuf.push_back(0);
            }
            graph.push_back(vbuf);
        }

        for (int i = 0; i < M; i++){
            int a, b;
            cin >> a >> b;
            a--; b--;
            graph[a][b] = 1;
        }
        int smallsize = INF;
        map<int, int> lastret;
        while (true){
            vector<int> parent;
            parent.clear();
            bfs(0, graph, parent);
            vector<int> ret = solve(N - 1, parent);
            if (smallsize>ret.size()){
                lastret.clear();
            }
            if (smallsize >= ret.size()){ smallsize = ret.size(); }
            if (ret.size() == 1000000){ break; }
            for (int i = 0; i < ret.size(); i++){
                lastret[ret[i]] = 1;
            }
            for (int i = 0; i < ret.size() - 1; i++){
                int a = ret[i];
                int b = ret[i + 1];
                graph[a][b] = 0;
            }
        }
        map<int, int>::iterator it;
        vector<int> finalret;
        for (it = lastret.begin(); it != lastret.end(); it++){
            finalret.push_back(it->first + 1);
        }
        for (int i = 0; i < finalret.size() - 1; i++){
            cout << finalret[i] << " ";
        }
        cout << finalret[finalret.size() - 1] << endl;


    }
    system("pause");
}