D不是同余最短路吗？？

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <string>
#include <map>
#include <string>
#include <set>
#include <queue>
#include <cmath>
#include <tuple>
#include <stack>
#include <numeric>
#include <climits>
#include <deque> 
#include <chrono>
#include <unordered_map>
#include <cstring>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#define systemwait system("read -p \"Press Enter to continue...\"");
#else
#define debug(x...) 
#define systemwait
#endif

#define int long long
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define sqsq(x) (x)*(x)
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>

const int INF=1e9+7;
const int MOD=1e9+7;
//const int MOD=998244353;
const int maxn=5005;

vi mp[maxn],vis[maxn];
vii dist[maxn];
pii ans;
int deg[maxn],N,M;

pii min(pii first,pii second) {
    if(first.first<second.first || (first.first==second.first && first.second<second.second)) {
        return first;
    }
    return second;
}

void Dijkstra(int src,int rmn) {
    priority_queue<pii,vii,greater<pii>> pq;
    dist[src][rmn]={0,0};
    pq.push({0,src});
    while(!pq.empty()) {
        auto [l,u]=pq.top();
        pq.pop();
        if(vis[u][l%deg[u]]) {
            continue;
        }
        vis[u][l%deg[u]]++;
        int pos=0;
        for(int v:mp[u]) {
            int t=(deg[u]+pos-(l%deg[u]))%deg[u];
            if(dist[v][(l+t+1)%deg[v]].first>(dist[u][l%deg[u]].first+t+1)
                || (dist[v][(l+t+1)%deg[v]].first==(dist[u][l%deg[u]].first+t+1) && dist[v][(l+t+1)%deg[v]].second>dist[u][l%deg[u]].second)) {
                dist[v][(l+t+1)%deg[v]].first=(dist[u][l%deg[u]].first+t+1);
                dist[v][(l+t+1)%deg[v]].second=(dist[u][l%deg[u]].second+t);
                pq.push({dist[v][(l+t+1)%deg[v]].first,v});
            }
            pos++;
        }
    }
}

void solve() {
//--------Initiallize Boundless--------
    memset(deg,0,sizeof(deg));
    ans={0x3f3f3f3f3f3f3f3f,0x3f3f3f3f3f3f3f3f};
//--------Input--------
    cin>>N>>M;
    for(int i=1;i<=N;i++) {
        mp[i].clear();
    }
    for(int i=1;i<=M;i++) {
        int uu,vv;
        cin>>uu>>vv;
        deg[uu]++;
        deg[vv]++;
        mp[uu].push_back(vv);
        mp[vv].push_back(uu);
    }
    for(int i=1;i<=N;i++) {
        vis[i].assign(deg[i],0);
        dist[i].assign(deg[i],{0x3f3f3f3f3f3f3f3f,0x3f3f3f3f3f3f3f3f});
    }
    // for(int i=1;i<=N;i++) {
    //     for(int j=0;j<N;j++) {
    //         vis[i][j]=0;
    //         dist[i][j]={0x3f3f3f3f,0x3f3f3f3f};
    //     }
    // }
//--------No fluff real stuff--------
    Dijkstra(1,0);
    for(int i=0;i<deg[N];i++) {
        ans=min(ans,dist[N][i]);
    }
    cout<<ans.first<<" "<<ans.second<<endl;
    return;


}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int TT=1;
    cin>>TT;
    for(int i=1;i<=TT;++i) {
        solve();
    }
    return 0;
}