#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10,M=N*2;

int n;

int h[N],e[M],ne[M],idx;

bool st[N];

int ans=N;

void add(int a,int b)

{

    e[idx]=b;

    ne[idx]=h[a];

    h[a]=idx++;

}

int dfs(int u)

{

    int i,j;

    //标记

    st[u]=true;

    //size表示当前子树的最大值

    //sum表示其子树所有点之和

    int size=0,sum=1;

    for(i=h[u];i!=-1;i=ne[i])

    {

        j=e[i];

        if(!st[j])

        {

            //获得其子树点和

            int s=dfs(j);

            //判断是否为最大

            size=max(size,s);

            //sum加上这个分支的总和

            sum+=s;

        }

    }

    //size比较其向上的其他点的最大值

    size=max(n-sum,size);

    //将当前最大值中去最小，即为我们所需答案

    ans=min(ans,size);

    return sum;

}

int main()

{

    //初始化

    memset(h,-1,sizeof(h));

    int i,j;

    cin>>n;

    for(i=0;i<n-1;i++)

    {

        int a,b;

        cin>>a>>b;

        add(a,b),add(b,a);

    }

    dfs(1);

    cout<<ans<<endl;

    return 0;

}

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10,M=N*2;

int n,m;

int h[N],e[M],ne[M],idx;

int d[N];

void add(int a,int b)

{

    e[idx]=b;

    ne[idx]=h[a];

    h[a]=idx++;

}

int bfs()

{

    int i,j;

    queue<int>q;

    //初始化距离全为-1，代表没有到该点

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

    //将1加入

    q.push(1);

    //起点到起点距离为0

    d[1]=0;

    while(q.size())

    {

        int t=q.front();

        q.pop();

        //遍历点到其他点

        for(i=h[t];i!=-1;i=ne[i])

        {

            j=e[i];

            //j是否到达了

            if(d[j]==-1)

            {

                //更新j的距离

                d[j]=d[t]+1;

                //将j加入队列

                q.push(j);

            }

        }

    }

    //直到到n，若到不了那还是-1，到了就是d[n]

    return d[n];

}

int main()

{

    int i,j;

    cin>>n>>m;

    memset(h,-1,sizeof(h));

    while(m--)

    {

        int a,b;

        cin>>a>>b;

        //有向边

        add(a,b);

    }

    cout<<bfs()<<endl;

    return 0;

}

#include<bits/stdc++.h>

using namespace std;

int n,m;

const int N=1e5+10,M=N*2;

int h[N],e[M],ne[M],idx;

int q[N],d[N];

void add(int a,int b)

{

    e[idx]=b;

    ne[idx]=h[a];

    h[a]=idx++;

}

bool topsort()

{

    //数组模拟队列

    int hh=0,tt=-1;

    int i,j;

    //将入度为0的点入队

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

    {

        if(!d[i])

            q[++tt]=i;

    }

    //遍历队列

    while(hh<=tt)

    {

        //获取头

        int t=q[hh++];

        //遍历与头连接的边

        for(i=h[t];i!=-1;i=ne[i])

        {

            j=e[i];

            //去掉t-j的边，因此j的入度减1

            d[j]--;

            //如果j的入度为0，则加入到队列

            if(d[j]==0)

                q[++tt]=j;

        }

    }

    //最后如果队尾=n-1代表，都加入到队列了

    return tt==n-1;

}

int main()

{

    int i,j;

    cin>>n>>m;

    memset(h,-1,sizeof(h));

    while(m--)

    {

        int a,b;

        cin>>a>>b;

        add(a,b);

        d[b]++;

    }

    if(topsort())

    {

        //数组存储的就是拓扑序列

        for(i=0;i<n;i++)

            cout<<q[i]<<" ";

    }

    else

        cout<<"-1";

    return 0;

}