1 #include<cstdio> 2 #include<vector> 3 #include<ext/pb_ds/priority_queue.hpp> 4 #define dis first 5 #define to second 6 const int N=20001,inf=0x7fffffff; 7 typedef std::pair<int,int> Edge; 8 int n,m,d[N]; 9 std::vector<int> e[N];10 void add(int a,int b) {11     e[a].push_back(b);12 }13 void dijkstra() {14     __gnu_pbds::priority_queue<Edge,std::greater<Edge> > q;15     __gnu_pbds::priority_queue<Edge,std::greater<Edge> >::point_iterator a[n+1];16     for(int i=1;i<=n;i++) {17         a[i]=q.push((i==1)?(Edge){0,i}:(Edge){inf,i});18         d[i]=(i==1)?0:inf;19     }20     while(!q.empty()) {21         Edge x=q.top();22         q.pop();23         if(x.dis==inf) continue;24         int u=x.to;25         for(std::vector<int>::iterator i=e[u].begin();i<e[u].end();i++) {26             int& next=*i;27             if(d[u]+1<d[next]) {28                 d[next]=d[u]+1;29                 q.modify(a[next],(Edge){d[next],next});30             }31         }32     }33 }34 int main() {35     scanf("%d%d",&n,&m);36     for(int i=1;i<=m;i++) {37         int a,b;38         scanf("%d%d",&a,&b);39         add(a,b);40         add(b,a);41     }42     dijkstra();43     int id,dis=0,count=0;44     for(int i=1;i<=n;i++) {45         if(d[i]==dis) count++;46         if(d[i]>dis) {47             id=i;48             dis=d[i];49             count=1;50         }51     }52     printf("%d %d %d\n",id,dis,count);53     return 0;54 }