100114J

经过思考后，很明显，我们可以看出应该是求出两条最长的链，链是指挂在连通块上的aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAbMAAAEOCAIAAACM2257AAATBElEQVR4nO3dL3MqSRfH8YitW8isQ1KrIlP7CpDIyMhIJPK6yMgrkbwEJBK5Mi/hkUgkkkeQmkyaoek/p7tP93w/bmth5vQ5Pb8LSRgezgCAnx5KFwAA6pCMAGAiGQHARDICgIlkBAATyQgAJpIRAEwkIwCYSEYAMJGMAGAiGQHARDICgIlkBAATyQgAJpIRAEwkIwCYSEYAMJGMAGAiGQHARDICgIlkBAATyQgAJpIRAEwkIwCYEibjww3pzggAIuRz6lYgEpEAaiEZT+6ZSD4C0EwmmMIykXwEoJNAJMXHIuEIQJXYPPINO8IRgH5RYRQTcIQjALXCk0gk1whHAApJJmPZ4wCAFBVxRjgCUCUkg1IEGeEIQI+0ybjb7Waz2cPDw2w2W61Wh8PB/bABhQGACIHfmVgefInFzq9fv/7555/NZhN/ZABIJ20yfnx8XD/+r7/+cjy4b20AICI2GR2ftd1un5+fu2fdeltNMgLQIFMyns/n0+nUPWu9XrscnHAEUIRf9ETGVvfE+Xye6BQAEK9MMlqeSzICKK5MMv7777+JTgEA8cok42QySXQKAIiXLxl3ux3vpgFUIV8yTqdTkhFAFfIlo+NzSUYAxWlPRoJSGwaEMYhKN68rweWJ9quOa7IIJoIRyvcZGJcnBl+EXKIp0PyxYY6dUSTjLb5rHw9aPRIM9Ja099qxPNHlyAX5tqUZdHUMmOld+e7pffcpLscUnGiwgI5VIX75I29gFUJ3/ehmqiUZ43udZOCefGvWQ3xdrTaqanI7vf2x5vuGLMvjU7c4yS7wJLsiWenKrrcnjRHZpbXvcy9iyejb1phDSXHcLqnlWaxvB6o7Czqpt5/a/SxIuC+WZ00mk+5hr6+vlkOFrEOa195Kp8gyc54rwxqbV3B3Fdy6qSX5cd7gE7vvhHl9fe3f37u6hnptvnQSLST+sKrO2B4lm8elHsGz5Jf2Fx2+T5dYUUlezUknrNTrx2w2G+PbHy9cviM38tS4KLI3BOtMdLoMFP0KOMXy9EjXt4De3n3A+Xxer9f2Y04mk9+/f59OJ5FuhPS0OTLDvq1I/alPmoj8z191zkyzFP20dNix/8Zd4255enr677//RJYc1cQKhc/SX9lFZTu7IMnfTSufWY1S9NlxBN3/vX5VaHxH7sPDQ8Cb67HtBMFR2luXtLG73W42m81ms81m475SwQKyCS/61oTCxglf7n3ud9t9CncfsNlsHh8fjaPNZrOPj4/gJXh1QDPf6XjxOq/surp3EpYvLMlQRgZRFdvHFjBXiHAfistBLI85HA6LxeL6dJ+fn/GlVuTWVhcRU0bYci6/eRt8Ydgdeblc5immlCQfchCpDOK8JuU+zf1+P5/P+4d9eXlJUZISwwEmRLYw3yN8fn6+vb11T79+Yeh+ZPHVZVbln8UhjNeMAkb5+fkZ8CzlO2dwe0tJWqfLs47H4/v7++DfZg0exOvgSdebmkytqaeOeL4DirzA0hWW1K2AEJGzbJdn7Xa7658UXzw9PT0MvWX2XUvOJsgSKzTzVoAv39E4PvKSicYF1n36M1FtUgY3rZRsqxhcyN2nHA6H/gd2L6bT6XK53O/3d0+UrjAlkn9OSPD4iOE7F5dHrtfr6xcdl09/Jq0tzOD+lJKo5rB1uTxruVxeHjydTi1/gnPrXKnLK064Sm2bBh3fodx95Pv7e/+A9r9xk60t4JiyRCqU4lue8aHP7XYbcK6YCr2eW4p8lfp30ggFjKN7sPEn3Ncfpo7JxJgKLU+XFbm01LyqNf49WywWYedKV6ESSaqscXu1LWAW3Q+hJpPJJfgGbzCxWCzCPjodU+GtCBMRv5acvOo3Pgsf8HOPblf873//S1SkEll/ppPoXLgrYBCr1ar/FOM/gy+tgAoH95IUkeIL8lpO9wmW4H/Puj9c9X2XUF3bs/4lQRUdaVLYFLbb7eB9JQQD8VaFicjWrIH7Avvvo4PH1x3k7e0tUZ1KpC1xJLtTP68R3Lot44Pce+e7FYpIUac2jkvux6Lv31T17ff7y0Fms1mKOvVIXuJot6wq7v2/dVtGkV+zuFcYIF1tmrk0oT/TyH/bTqdT96NG91uHuJeqR4762MfFuTffePt8909/E1VIDrpw7InjrTal3PpH1LFaJTLVN9jBPKfG2WdTdq8IAu5HG8N+seWspCKOXbr+rEtqg/coc6xWicKfxMp29pFzb/vr62vkVRH2vpuNEcCxad2X02UzeI8yx2qVKPzpTv0NaoZj2/v3ywlmv61pcG0wlOpb2BnrmnLu+gYvpMw1jJN7z7tP1Aa7e1vT4NrQV6pv3dtzr6+4qGvKBeobvJbylzE2mhuuuTbNSvWtu5H7er12f1ZdUy5TH+GYn9qGqy1Mv1J922w2lzPO53P3Z9U15WL1EY756ey2zqqqUKp1x+Mx4KR1DVrXfeX096tqCrutsKSKFGwdyZj49IRjRgpbrbCkupCMiZSvj3DMSVWrVRVTqVIN9D1jdYNWUSLhmJOSVispo3YkYyJaSiQcs1HSZyVl1I5kTERRiYRjNsX7XLyAZhTp5OFw8DpdjePWVSLhmE3BPjNiWfmb2d3g/fn52eXxNY5bXZWEYx6DfY5ptcsRxE+Kc4nc6W5r5vi9gzWOW2OVXDx5COaUyxGIxUQyt9T3tt6VTlxplVxCeUil1d2nE4tJ5Wzs29vb5RS/f/9WVZgsvYVyIeVxK7O8um15rsjxYZett/0vTnC5t3G9Q1ddKJdTNpb8cuy5/QgMMbU8Te5/L6uSkhLRXivXVTaRieaciowviQx97v+xjsvXbFU9+gpq5erKxj3dgpVeYstSd7u7pbHLH+vUPvo6yuUay0kwB5lXZuna3v/G6rt/rNPA9KupmIstM6lAZEyZpei/8Y3VvgXUuAdqqriNjleHTKxLwCDuPqz/ixf7Txib2QaVFd1M3ytFOFbBaxAuD+v+70hi8VxdMp7b6n6TGI0Gjv9QuVxK/bfSkaerSJWlNzaDxjAaJW6lVX8iLsOazWaX//X6+hp2lhrVWn17k2gJc1HCHluOV9Dlt9IvLy/Xb6VbjcVzvcl4JhwVYy6qWPLLcUaHw8HrgIkXlEPda2h1Kg1gKKpEJqPgQWpR/UraHk+9GIo2LrkWqfQSJbWwmOaHVCkmohCZ6KiRJY1kWnVhIgqRiY7aWdioxlYFxqENgeiuqRWOc4SaMQtV7FcHadjX2mqZqCrMQg9m4aXB7hCOqjAIDbgifLXZIMJRDwZRHJdDgGYbxG7QgymUxYUQoOUeEY5KMIWCaH6YxttEOCrBCIpg8wdrv1OEowaMID92foxRdIotogH9z4w9H2MszSIci6P/OdHtSCPqF+FYFs3PhlbHG1fLCMey6HwGbHIRo2sZ+6YgOp8BTRYxxq4RjgXR9qTY2FJG2jjCsRTang69FTTe3hGOpdDzFNjPskbdOzZTEfQ8Bboqa+ztIxyLoOGy2MPi6CDhWAANF0QzU6CJ5zPhWALdFsHWTYQmfmGHZUa3RdDGROjjN8IxJ1odjx6mQyt/IBxzos8x2KhJ0U0T4ZgNfQ7GLk2Nbg5g22VDk8OwP1OjocMIxzxocgCalgE9vYlwzIMOe2FP5kFbbQjHDOiwOzZkNrT1DvZiBrTXEVsxGzp7H+GYGu11QZdyorlOCMfU6K0d2y8z+uuKcEyKxlqw9/Kjvx7cN+jgI9nNFvTKgubkR4v93Mq7W1FoV3o1utCcQWybIuiyt7AQJCLvoi3X6EkpNDoE4ZgIPeljnxREo0OkSEb2/ZmXSD/RjYLotZ/IgCMf76IVF+yKsmi3B9lcIxwH0YozTVCAjrtyjEXffUw4Xht5H9gMGtBxJ/bwit/KhGPfyPsw8uUrQdPvc8kskVwjHDujbQIbQAn6fod7WhGOgsbZAUavB6238c0pkZ1NOJ5HmRHMXRVaf1PYThXZ2Vwk5/G9bGTiqtD9m4J3qsjO5joZVQdGtdgqMIBhGnaqhhrKGsnyGbRCzGCAnp2qp5IixrD86zU2uczqMIMBenaqnkpKaX75jFgnxmDStlO11ZNZ28tve3VVYxImhZtVWz2Ztbp8hTsNHYbxQ/Bm3e/38/l8tVodDgc9VbWhyeVfL6qNdTWDYfwQvFnn8/nl8b9+/fr7778H9/1ds9lss9m4FCa24Eq0t3xiUTnm8UPwZn1/fw9LQ8NkMpEtrA2NLZ9Y1I+R/BCzX7fbbXwyLpdLl8LGdi21tPyW1tIwpvItfr8m3esjv5zaWP7gP4eli8IApvKNZNSsjUBpYxVjwGC+kYzK1d4BYrEizOYbyahc1clSdfEjxHi+iOza1JueS6vSDhCL1WFCX0jGKtQYMdc1V1H2yDGhLyRjLaprArFYI4b0hWSsRV1BU1e16DCnLyLbdzKZXJ5+99PTx+Px/f19NpsZ57V8QFCqyAbU0gdisV6M6ovIDl4sFpenr9frwQd8fn6uVqvrQOy79QFBqSIbUEUfBodbuii4YlRfRHbwZrOxRJ67pEU2oIrEqaJI3MK0vohs4uPx2L2hvuv6jTPJ6E55K4jF2jGwL1L7eLlcWtJwOp0ul8v9fm+vIXWRDdAcPZprgyNm9kXDViYZvejsxuC/iKWLgjdm9q34brafmuvN4NuQwcwS7yRjagNj+1Z2Qx8OB69kzFyeTvaeWKLQTqoexlQvJvet4J7ebrfdn/I8Pz9rK0+twSQKDsTIXIt8OlRheN9KbevD4dD/jfZ2u1VVnnKCOXhLcBmp1450GN4PRXZ2/9fZi8XCpTCuuo5gAtr5lpFn+UiE+f2Qf3P3v1rr1qvFIoXVQiTaIg/idS5UgRH+kHl/92Px1qvFIoXVIiYNg49pHJZYbBJT/CHnLjdi8XQ6aaiqFuKBGHaKdGdHWUzRlGeXu8ditpIqYs8s2RbZz0IstopBmlLv9ePxuFqtgmORa+9uLKboUpGToiBmOSDFjh+8ISOx6MsSSRkaRSyOB+McELnpd7ud/Q6MjrEYX0lj7HmUp1Ek40gwzmEx+/5uLNpv3C1SQ3tcwihPo4jFMWCiNwXv/o+Pj5hAjDx7k1SF0WAxIx9QexjnTQV3PxeeQU83bsUiM2oMs7Qpsvu55AyqukEyjgSzvCPzBcD1ZhDphuWbGler1d0verTXw7CaxCDvy3YBcKVdi2/Ibrd7fHy0ZNlkMvn4+AgoabBC3/KgE4N0kvoFQurjVyq+IcYd3izhWLBIKMQUXVmuK4WHbUN8Q7o7vE2n0+s/DNhut4mGGHM0aMAIPVhSLOBikD1aeyJ7YnwK8+79gAuWCoUYoR97nLlcFfFHGIngnvS/OuLCcoc3qZ4zwcYwwhAu6Ram9Mq0CO7M9Q8WHe/wVqpg6MT8wpGJ6QQ3p//VES4fOhLsPwNtCfOLQiwmEtYfx6+OGDxRRLHmoZhpA5ifDAJRUFij3L86YvBcEfWah2K+DWB48kjDSAEdW6/X/Vi8e3u363NF1DtwNGZdO4YHdQLyZTqdBsRiP08j6v1GMjaD4UEd33z5/Py8PPLx8dE9Fs+9PH19fY2o9xvJ2AyGB3V88+XPnz+XR768vLifpf9zSa88tSMc28DkoEvAC8bn5+fLg//8+eN4ln4sSr1gvCAZ28DkoIt7suz3e+OzLp+fny6n8PpKW18kYxuYHHRxTJbrz7rM5/O7B/f9StsAJGMbmBx0cUyWLuCm0+lyudzv9/bDXn+hY4pYPJOMrWBy0MUxWbpfKzt+1sWIxaenpxSxeCYZW8HkoItjsvhGj+ULHdfrtVDtPwojGavG5KCLY7J0P2T0OvjpdFosFtf56PVtB3YkYxuYHHRxTJbLa8Dlcul7/NPp9Pb2Zpwl5tsODCRjG5gcdMmZLKfTqXvt6fUNghYkYxuYHNTJGS7dm2upnzaSjG1gclAnZ7hsNpvLWVz+HPIuYrEZDA/q5MyX4/HYvaGO/z0MydgMhgd1MudL9wUJ8b+HIRmbwfCgzsOVpKc7nU4iJ8pcNpJieNAoc8SkSEap2lAE84NGJCPKYn7QKMM70+Px+P7+bnyeOvhovJVuDPODUmFBM5h37jJXC7UYIZS6G1vXNxaLFPBZQ8dSUR1GCL3scRMfi7PZbLPZiNdJMjaAEUIve+JYbiwmknciRaJSTBGq6Q8d/RUiAIOEaspfkSkvD8EYJLRTmz5qC0M8ZgntBn+YWLoopVVBCrNEBbTFkLZ6II5xog56wkhPJUiHiaIaGiJJQw3IgKGiJmWDiVgcD+aKygzGU+qEKnJSFMRoUZ9bOZUiqnKeC3owXVTJElhSmZXhFFCLAaNW9uQKzq9Eh0VdmDHq5hJkLlkmdRy0gUmjBY65FqP0EpEV80YjiEUIYuRoDYGIeMwezSIQEYxNgFEgDeGFDQEAJpIRAEwkIwCYSEYAMJGMAGAiGQHARDICgIlkBAATyQgAJpIRAEwkIwCYSEYAMJGMAGAiGQHARDICgIlkBAATyQgAJpIRAEwkIwCYSEYAMP0fGEFwisNJJ+QAAAAASUVORK5CYII=" alt="" />

1,5可以称作一条链，但是，图里会有连通块，也就是环或者几个环相交在一起，这时就很难求链。这时，需要进行缩点。

缩点是把连通块变成一个点，大概是通过tarjan求出桥，也就是删掉这条边之后，图变得不连通，求出桥之后，把这些边删掉

然后通过dfs把每个连通块标记成一个颜色，也就是一个新的点，这时，所有的点都不联通，都有了新的编号，那些割点也是

然后就两次bfs求树的直径就可以了

#include<iostream>

#include<cstring>

#include<Vector>

#include<Queue>

#include<cstdio>

#define N 10010

using namespace std;

int n,m,all_edge=-,time,x,cnt;

int to[*N],next[*N],head[*N],color[*N],num[N],d[N],low[N],dfn[N],cut[*N];

queue<int>q;

vector<int>graph[N];

inline int min(int x,int y){return x<y?x:y;}

inline void ins(int u,int v){to[++all_edge]=v;next[all_edge]=head[u];head[u]=all_edge;}

inline void insert(int u,int v){ins(u,v);ins(v,u);}

void tarjan(int u,int fa)

{

    dfn[u]=low[u]=++time;

    for(int i=head[u];~i;i=next[i])

    {

        int v=to[i];

        if(!dfn[v])

        {

            tarjan(v,u);

            low[u]=min(low[u],low[v]);

            if(low[v]>dfn[u]){cut[i]=cut[i^]=;}

        } else if(v!=fa)low[u]=min(low[u],low[v]);

    }

}

void dfs(int u)

{

    color[u]=cnt;

    for(int i=head[u];~i;i=next[i])

    {

        int v=to[i];

        if(!color[v]&&!cut[i]) dfs(v);

    }

}

void bfs(int point)

{

    int MAX=;x=;

    memset(d,-,sizeof(d));

    q.push(point);

    d[point]=;

    while(!q.empty())

    {

        int u=q.front();q.pop();

        for(int i=;i<graph[u].size();i++)

        {

            int v=graph[u][i];

            if(d[v]==-)

            {

                d[v]=d[u]+;

                q.push(v);

                if(d[v]>MAX){MAX=d[v];x=v;}

            }

        }

    }

    cout<<num[x]<<" ";

}

int main()

{

    freopen("input.txt","r",stdin);

    freopen("output.txt","w",stdout);

    cin>>n>>m;memset(head,-,sizeof(head));

    for(int i=;i<=m;i++)

    {

        int u,v;

        scanf("%d%d",&u,&v);

        insert(u,v);

    }

    tarjan(,-);

    for(int i=;i<=n;i++) if(!color[i])

    {

        ++cnt;

        num[cnt]=i;

        dfs(i);

    }

    for(int i=;i<all_edge;i+=) if(cut[i])

    {

        int u=color[to[i^]],v=color[to[i]];

        graph[u].push_back(v);

        graph[v].push_back(u);

    }

/*    cout<<"---------"<<endl;

    for(int i=1;i<=cnt;i++)

    {

        cout<<"i="<<i<<":";

        for(int j=0;j<graph[i].size();j++)

        {

            cout<<graph[i][j]<<" ";

        }

        cout<<endl;

    }

    cout<<"---------"<<endl;*/

    bfs();

    bfs(x);

    fclose(stdin);

    fclose(stdout);

    return ;

}