#include<bits/stdc++.h>

using namespace std;

vector<vector<int> > t(510);

int bfs(int a, int b){
    vector<bool> vis(510,false);   //每条边的权值都是1，直接用二维数组存。本来是还有存一个len的，现在不用了，就直接二维数组
    queue<int> q;
    q.push(a);
    vis[a]=true;
    int level=0;
    while(!q.empty()){
        int k=q.size();
        for(int i=0;i<k;i++){
            int temp = q.front();
            q.pop();
            for(int i=0;i<t[temp].size();i++){
                int next = t[temp][i];
                if(next==b){
                    return level+1;
                }
                if(vis[next]==false){
                    vis[next]=true;
                    q.push(next);
                }
            }
        }
        level++;
    }
}

int main(){
    int T;
    cin>>T;
    while(T--){
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            int t1,t2;
            cin>>t1>&...