// Problem: E. Cactus
// Contest: Codeforces - Codeforces Round #143 (Div. 2)
// URL: https://codeforces.com/contest/231/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms

/*

WINNERS NEVER QUIT AND QUITTERS NEVER WIN!!

Falling down is an accident, Staying down is a choice.

*/
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include "bits/stdc++.h"
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>*/

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vb> vvb;
typedef vector<vll> vvll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef unordered_map<ll,ll> umll;
template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
/*template <typename num_t>
using ordered_set = tree<num_t, null_type, less<num_t>, rb_tree_tag, tree_order_statistics_node_update>;*/
// find_by_order(k): iterator to the kth largest(0 indexed). order_of_key(k): no. of items < k

#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define FOR3(i,a,b) for(long long i=a;i<b;i++)
#define FOR4(i,a,b,step) for(long long i=a;i<b;i=i+step)
#define REV3(i,a,b) for(long long i=a;i>=b;i--)
#define REV4(i,a,b,step) for(long long i=a;i>=b;i=i-step)
#define FOR(...) GET_MACRO(__VA_ARGS__, FOR4, FOR3)(__VA_ARGS__)
#define REV(...) GET_MACRO(__VA_ARGS__, REV4, REV3)(__VA_ARGS__)
#define F first
#define S second
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define tc ll tests;cin>>tests;while(tests--)
#define io ios_base::sync_with_stdio(false);cin.tie(nullptr);
#define coutv(v) for(auto it: (v))cout<<it<<" ";newl;
#define cout2d(v) for(auto it: (v)) {for(auto j:it) cout<<j<<" ";newl;}
#define cinv(v,n) vll (v)(n);FOR(i,0,(n)){cin>>v[i];}
#define cinvg(v,n) (v).resize(n);FOR(i,0,(n)){cin>>v[i];}
#define cin2d(v,n,m) vvll (v)(n,vll(m,0));FOR(i,0,n){FOR(j,0,m){cin>>v[i][j];}}
#define cin2dg(v,n,m) (v).resize(n,vll(m));FOR(i,0,n){FOR(j,0,m){cin>>v[i][j];}}
#define pyes(CONDITION) cout << (CONDITION ? "YES" : "NO") << '\n';
#define newl cout<<"\n"
#define MOD 1000000007
#define INF LLONG_MAX/2
#define m1(x) template<class T, class... U> void x(T&& a, U&&... b)
#define m2(x) (int[]){(x forward<U>(b),0)...}
m1(pr) { cout << forward<T>(a);  m2(cout << " " <<); cout << "\n"; }
m1(re) { cin >> forward<T>(a); m2(cin >>); }
template <class ...Args>
auto &readd(Args &...args) { return (cin >> ... >> args); }
#define re(...) __VA_ARGS__; readd(__VA_ARGS__)

const ll dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};
// const ll dx[8] = {-2,-1,1,2,2,1,-1,-2}, dy[8] = {1,2,2,1,-1,-2,-2,-1}; //knight moves

// ************************DEBUG START********************************
#ifndef ONLINE_JUDGE
//#define cerr cout
#include "myprettyprint.hpp"
#else
#define dbg(...)
#endif
// ************************DEBUG END**********************************

constexpr ll pct(ll x) { return __builtin_popcountll(x); } // # of bits set
constexpr ll bits(ll x) {return x == 0LL ? 0LL : 63LL-__builtin_clzll(x); } // floor(log2(x))
constexpr ll p2(ll x) { return 1LL<<x; }
constexpr ll msk2(ll x) { return p2(x)-1LL; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct LCA
{
    ll n, LOG, timer = 0;
    vvll g, up;
    vll tin, tout;
    vll lev;

    void init(ll x)
    {
        n=x;
        timer=0;
        LOG = ceil(log2(n));
        g.resize(n);
        up.resize(n, vll(LOG+1));
        tin.assign(n,0);
        tout.assign(n,0);
        lev.assign(n,0);
    }

    void init(vvll adj)
    {
        n = adj.size();
        g = move(adj);
        timer=0;

        LOG = ceil(log2(n));
        up.resize(n, vll(LOG+1));
        tin.assign(n,0);
        tout.assign(n,0);
        lev.assign(n,0);
        dfs();
    }

    void dfs(ll u=0, ll p=0)
    {
        tin[u]=timer++;
        up[u][0] = p;
        FOR(i,1,LOG+1)
        {
            up[u][i] = up[up[u][i-1]][i-1];
        }
        for(auto v:g[u])
        {
            if(p==v) continue;
            lev[v] = lev[u] + 1;
            dfs(v,u);
        }
        tout[u]=timer++;
    }

    bool is_ancestor(ll u, ll v)
    {
        return tin[u]<=tin[v] && tout[u]>=tout[v];
    }

    ll lca(ll u, ll v)
    {
        if(is_ancestor(u,v)) return u;
        if(is_ancestor(v,u)) return v;
        REV(i,LOG,0)
        {
            if(!is_ancestor(up[u][i], v)) u = up[u][i];
        }
        return up[u][0];
    }

    ll dist(ll a, ll b)
    {
        ll l=lca(a,b);
        return lev[a]+lev[b]-2*lev[l];
    }

    ll lift(ll u, ll d)
    {
        while(d>0)
        {
            ll raise=log2(d);
            u=up[u][raise];
            d-=(1LL<<raise);
        }
        return u;
    }
};

vvll g;

void test()
{
    ll re(n,m);
    g.resize(n);

    FOR(i,0,m)
    {
        ll re(u,v);
        u--;v--;
        g[u].pb(v);
        g[v].pb(u);
    }

    LCA lca;
    lca.init(g);
}

int main()
{
    io;
    ll tests=1;
    //cin>>tests;
    while(tests--)
    {
        test();
    }
    return 0;
}