#include<iostream> #include<queue> #include<cstring> using namespace std; const int N = 1000010; int h[N],e[N], ne[N], idx=0; int d[N]; int m, n; queue<int>q; //链表连图是将节点和下一层所有节点相连 void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } int bfs() { q.push(1);//起始位置 d[1] = 0;//第一层为0 while (!q.empty()) { int t = q.front();//注意不要放反,先取出再弹出 q.pop(); for (int i = h[t]; i != -1; i = ne[i]) {//走下一层所有节点 int j=e[i];//把下一节点 节点值取出 if (d[j] == -1) { d[j] = d[t] + 1;//没遍历过就记录深度,注意是上一节点层数+1 q.push(j);//把节点存入,等待遍历 } } } return d[n]; } int main() { memset(d, -1, sizeof d); scanf("%d%d", &n, &m); memset(h, -1, sizeof h); for (int i = 0; i < m; i++) { int a, b; scanf("%d%d", &a, &b); add(a, b); } cout << bfs() << endl; return 0; }