local read = setmetatable({}, {__index = function(t, k) local a = {} for i=1,#k do table.insert(a, '*'..string.sub(k, i, i)) end local r = io.read local u = table.unpack or unpack return function() return r(u(a)) end end})
read.N = function(N) local t={} for i=1,N do t[i]=read.n() end return t end
----
local readnn = read.nn
local readn32 = read[("n"):rep(32)]
local N, Q = readnn()
local edges = {}
for i=1,N//16 do
    edges[i] = {} edges[i+1] = {} edges[i+2] = {} edges[i+3] = {}
    edges[i+4] = {} edges[i+5] = {} edges[i+6] = {} edges[i+7] = {}
    edges[i+8] = {} edges[i+9] = {} edges[i+10] = {} edges[i+11] = {}
    edges[i+12] = {} edges[i+13] = {} edges[i+14] = {} edges[i+15] = {}
end
for i=(N//16)+1,N do
    edges[i] = {}
end
local insert = table.insert
for i=1,(N-1)//16 do
    local a1,b1,a2,b2,a3,b3,a4,b4,a5,b5,a6,b6,a7,b7,a8,b8,
            a9,b9,a10,b10,a11,b11,a12,b12,a13,b13,a14,b14,a15,b15,a16,b16 = readn32()
    insert(edges[a1], b1)
    insert(edges[b2], a2)
    insert(edges[a3], b3)
    insert(edges[b4], a4)
    insert(edges[a5], b5)
    insert(edges[b6], a6)
    insert(edges[a7], b7)
    insert(edges[b8], a8)
    insert(edges[b9], a9)
    insert(edges[a10], b10)
    insert(edges[a11], b11)
    insert(edges[a12], b12)
    insert(edges[a13], b13)
    insert(edges[a14], b14)
    insert(edges[a15], b15)
    insert(edges[a16], b16)
end
for i=((N-1)//16)+1,N-1 do
    local a,b = readnn()
    insert(edges[a], b)
end
