因为这题走到下一个点只有换乘次数+1或者不变两种变化，所以用dfs也可以做，遍历到需要换乘的先记录，等处理完不用换成的再处理需要换乘的

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

const int N = 510,M = 50010;
int h[N],e[M],ne[M],w[M],idx,line_cnt;

int n,m;
int dist[N];

void add(int a,int b){
    e[idx] = b;
    w[idx] = line_cnt;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dfs(int u,int len,int last){
    vector<int> defers;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j = e[i];
        int line_num = w[i];
        if(last == -1){
            if(dist[j] >= len){
                dist[j] = len;
                dfs(j,len,line_num);
            }
        }else{
            if(line_num == last){
            //这里必须要用>= 用>不行，因为上一次走到这里可能是走别的路线过来的，所以不能
            //走一次就不再更新了，因为不同的路线也会影响后续的dist，所以不同路线走来都要更
            //新一次
            //比如上面的样例，第一次走到47是2号线转1号线转0号线，这是用47更新50，还要再转到3号线，50是3
            //如果不用>=，下一次走到47是2号线，转1号线，转3号线，再走到50不用再转，就是2。
                if(dist[j] >= len){
                    dist[j] = len;
                    dfs(j,len,line_num);
                }
            }else{
                if(dist[j] >= len+1){
                    defers.push_back(i);
                }
            }            
        }


    }

    for(int i:defers){
        int j = e[i];
        if(dist[j] >= len+1){
            dist[j] = len+1;
            dfs(j,len+1,w[i]);
        }
    }
}

int main(){
    memset(dist,0x3f,sizeof dist);
    memset(h,-1,sizeof h);
    cin>>m>>n;
    for(int i=0;i<m;i++){
        string line;
        getline(cin,line);
        while(getline(cin,line)){
            stringstream ssin(line);
            int a,b,t;
            ssin>>a>>b;
            add(a,b);
            while(ssin>>t){
                a=b;
                b=t;
                add(a,b);
            }
            line_cnt++;
        }

    }
    dist[1] = 0;

    dfs(1,0,-1);

    if(dist[n] != 0x3f3f3f3f){
        cout<<dist[n];
    }else{
        cout<<"NO";
    }

}