f = File.open("input.txt","r")
(nv, ne, m)=f.readline.split
nv=nv.to_i  # кількість вершин
ne=ne.to_i  # кількість ребер
$b=[]       # списки суміжності
for k in 0...nv
  $b[k]=[]
end
for l in 0...ne
  (j, k)=f.readline.split
  j=j.to_i
  k=k.to_i
  $b[j].push(k)
  $b[k].push(j)
end
f.close
$f = File.open("output.txt","w")
$neo=[true]*nv # мітка "нова вершина"
$k =    [0]*nv # поточні номери ребер у списках суміжності
v0=0
$neo[v0]=false
v=v0
def step(v)
  while $k[v]<$b[v].length
    w=$b[v][$k[v]]
    $k[v]=$k[v]+1
    if $neo[w]
       $neo[w]=false
       $f.puts "#{v} #{w}"
       step(w)
    end
  end
  nil
end
step(0)
$f.close()