Untitled

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define endl "\n"
 
const double PI = 3.14159265358979;
const ll INF =  1e9 + 7;
const ll MOD = 1e9 + 7;
const ll nax = 2505;
const int LOG = 25;


vector<int> dijkstra(int src, int n, vector<pair<int, int> > adj[]) {
    vector<int> dist(n + 1, INF);
    vector<bool> visited(n + 1, false);
    deque<int> dq;

    dist[src] = 0;
    dq.push_back(src);

    while(!dq.empty()) {
        int current = dq.front();
        dq.pop_front();

        if (visited[current]) continue;
        visited[current] = true;

        for (auto neigh: adj[current]) {
            if (dist[neigh.first] > dist[current] + neigh.second) {
                dist[neigh.first] = dist[current] + neigh.second;
            }

            if (neigh.second == 0) {
                dq.push_front(neigh.first);
            } else {
                dq.push_back(neigh.first);
            }
        }
    }

    return dist;
}


void solve() {
    int n, m;
    cin >> n >> m;

    vector<pair<int, int> > adj[n + 1];
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        if (x != y) {
            adj[x].push_back({y, 0});
            adj[y].push_back({x, 1});
        }
    }

    vector<int> dist = dijkstra(1, n, adj);
    cout << (dist[n] == INF ? -1 : dist[n]) << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t; cin >> t; while(t--)
    solve();
    return 0;
}