#include <iostream>

 #include <vector>

 #include <algorithm>

 #define MAXN 100

 //2^MAXLOG2>=最大深度

 #define MAXLOG2 7

 using namespace std;

 vector<int>G[MAXN];

 int depth[MAXN];

 int ancestor[MAXN][MAXLOG2]; 

 void creat()//输入并存储树

 {

     int n,x,y;

     cin>>n;//n条边

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

     {

         cin>>x>>y;

         G[x].push_back(y);

         G[y].push_back(x);

     }

 }

 void dfs(int x,int father)

 {

     depth[x]=depth[father]+;//计算x深度

     ancestor[x][]=father;

     //计算x结点的2^i步祖先

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

         //因为是dfs，所以深度小的结点的ancestor总会先算出来

         //MAXLOG2太大了会怎样？因为ancestor[0][i]=0，所以不管怎样往上走都是0

         ancestor[x][i]=ancestor[ancestor[x][i-]][i-];

     for(int i=;i<G[x].size();i++)

         if(G[x][i]!=father)dfs(G[x][i],x);

 }

 int lca(int x,int y)

 {

     if(depth[x]<depth[y])swap(x,y);

     /*假设x与y深度相差z，x每次走2^i(i从最大每次循环减少1)步总能到达y的深度

     证明：将z转换成二进制，再转换成十进制

         则肯定等于2^i1 + 2^i2 + 2^i3 ... 形式  */

     for(int i=MAXLOG2-;i>=;i--)

         //如何防止走多了？走完后的深度比y还小，说明走多了，这时候我们就不走

         if(depth[ancestor[x][i]]>=depth[y])x=ancestor[x][i];

     if(x==y)return x;

     //假设x与LCA相距L步，那么x,y都走L-1步仍然不相等，下面的循环是让x,y走L-1步

     for(int i=MAXLOG2-;i>=;i--)

         /*如何防止走多了？

          注意循环结束条件，并非当x,y走完后相等

          如果以x,y相等为结束条件，则有可能会走过了

          此循环的目的是为了让x,y走L-1步

          LCA相当于x,y的中点

          为什么一定刚好走L-1步？

          首先能确定的是存在两个结点再往上一步就是LCA

          此循环让x,y只要不相等就往上走，x,y肯定会到达这两个结点

          即x,y走L-1步会到达那两个结点。自己可以画图试试*/

         if(ancestor[x][i]!=ancestor[y][i])

         {

             x=ancestor[x][i];

             y=ancestor[y][i];

         }

     return ancestor[x][]; //即x再向上走1（2^0）步即是LCA

 }

 int main()

 {

     creat();//数据要输入

     dfs(,);

     //cout<<lca(7,6);

     return ;

 }