Untitled

#include<bits/stdc++.h>
using namespace std;

// Simple Debugging Template
#ifndef ONLINE_JUDGE
#define pr_arr(a,n)cout<<#a<<":";for(int i=0;i<n;i++)cout<<a[i]<<" ";cout<<endl;
#define pr_mat(mat,row,col)cout<<#mat<<":\n";for(int i=0;i<row;i++){for(int j=0;j<col;j++)cout<<mat[i][j]<<" ";cout<<endl;}
#define pr(...)dbs(#__VA_ARGS__,__VA_ARGS__)
template<class S,class T>ostream &operator<<(ostream &os,const pair<S,T> &p){return os<<"("<<p.first<<","<<p.second<<")";}
template<class T>ostream &operator<<(ostream &os,const vector<T> &p){os<<"[";for(auto&it:p)os<<it<<" ";return os<<"]";}
template<class T>ostream &operator<<(ostream &os,const set<T>&p){os<<"[";for(auto&it:p)os<<it<<" ";return os<<"]";}
template<class T>ostream &operator<<(ostream &os, const stack<T>&s){os<<"[";stack<T> temp(s);while (!temp.empty()){os << temp.top();temp.pop();if (!temp.empty())os << ", ";}return os << "]";}
template<class T>ostream &operator<<(ostream &os, const queue<T>&q){os<<"[";queue<T>temp(q);int size=temp.size();for(int i=0;i<size;i++){T front=temp.front();os<<front;temp.pop();if(i<size-1)os<< ", ";temp.push(front);}return os<< "]";}
template<class T>ostream &operator<<(ostream &os,const multiset<T>&p){os<<"[";for(auto&it:p)os<<it<<" ";return os<<"]";}
template<class T> ostream &operator<<(ostream &os, const priority_queue<T>&pq){os<<"[";priority_queue<T> temp(pq);while(!temp.empty()){os<<temp.top();temp.pop();if(!temp.empty()){os<<", ";}}return os << "]";}
template<class S,class T>ostream &operator<<(ostream &os,const map<S,T>&p){os<<"[";for(auto&it:p)os<<it<<" ";return os<<"]";}
template<class T>void dbs(string str,T t){cout<<str<<":"<<t<<"\n";}
template<class T,class...S>void dbs(string str,T t,S... s){int idx=str.find(',');cout<<str.substr(0,idx)<<":"<<t<<",";dbs(str.substr(idx+1),s...);}
#else
#define pr(...){}
#define debarr(a,n){}
#define debmat(mat,row,col){}
#endif
// Debugging Template ends
#define f                       first
#define s                       second
#define ARRAY_INPUT(arr, n)     for(int i = 0; i < n; i++) cin >> arr[i]
#define FOR(i, j, k, inc)       for (int i=j ; i<k ; i+=inc)
#define fr(i,x)                 for(int i = 0; i < x;i++)
#define mip(x)                  ll x;cin>>x
#define ip(x)                   cin>>x
#define pb                      push_back

using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

using vi = vector<int>;
using vll = vector<long long>;
using vpii = vector<pii>;
using vpll = vector<pll>;

using vvi = vector<vector<int>>;
using vvll = vector<vector<long long>>;
using vvpii = vector<vector<pii>>;
using vvpll = vector<vector<pll>>;

using state = pll;

ll n,m;
vvll g;
vvll par;
vll dis;

void printer(deque<ll> &dq){
    cout << "dq:[";
    for(auto x:dq){
        cout << x <<" ";
    }
    cout << "]\n";
}

void bfs01(){
    dis.assign(n+1,1e9);

    deque<ll> dq;
    dq.push_back(1);
    dis[1] = 0;

//    printer(dq);

    while(!dq.empty()) {
        ll node = dq.front();
        dq.pop_front();

        // Forward link
        for(auto v: g[node]){
            if(dis[v] > dis[node]+0){
                dis[v] = dis[node];
                dq.push_front(v);
            }
        }

        // Backward link
        for(auto v: par[node]){
            if(dis[v] > dis[node]+1){
                dis[v] = dis[node]+1;
                dq.push_back(v);
            }
        }
//        printer(dq);
    }
}

void solve(){
    cin >> n >> m;
    g.resize(n+1);
    par.resize(n+1);
    fr(i,m){
        mip(a);mip(b);
        if(a==b) continue;
        g[a].pb(b);
        par[b].pb(a);
    }
    pr(g);
    pr(par);
    bfs01();
    if(dis[n] == 1e9) cout << "-1\n";
    else cout << dis[n] << "\n";

}

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

#ifndef ONLINE_JUDGE
    freopen("Input.txt","r",stdin);
    freopen("Output.txt","w",stdout);
    freopen("Error.txt","w",stderr);
#endif


    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
}
1
7 5
2 1
3 2
3 4
6 2
5 6