int bfs() { memset(cnt,0x3f,sizeof cnt); cnt[1]=0; q.push({0,1}); while(q.size()) { auto t=q.front();q.pop(); int ver=t.second; if(st[ver])continue; st[ver]=true; for(int i=h[ver];~i;i=ne[i]) { int j=e[i]; i...