$susedia = []

def pridaj_hranu(a, b)
  $susedia[a] = [] if not $susedia[a]
  $susedia[b] = [] if not $susedia[b]
  $susedia[a] << b; $susedia[b] << a
end

def existuje_cesta(zaciatok, koniec, zakazane)
  return false if zakazane.member? zaciatok or zakazane.member? koniec
  navstivene = Array.new($N); navstivene[zaciatok] = true
  fronta = [zaciatok]
  teraz = nil
  while true
    teraz = fronta.shift
    return false if teraz == nil   # uz sme minuli frontu a stale nic
    ($susedia[teraz] - zakazane).each do |sused|
      return true if sused == koniec
      if not navstivene[sused]
        fronta << sused
        navstivene[sused] = true
      end
    end
  end
end

def najblizsi_nenavstiveny_bod(navstivene, vzdialenosti, zaciatok)
  return zaciatok if not navstivene[zaciatok]
  min = nil
  vzdialenosti.each_with_index do |vzd,i|
    next if navstivene[i] or vzd == nil
    min = i if min == nil or vzd < vzdialenosti[min]
  end
  return min
end

def najdi_cestu(zaciatok, koniec, zakazane)
  return nil if zakazane.member? zaciatok or zakazane.member? koniec
  # http://en.wikipedia.org/wiki/Dijkstras_algorithm
  vzdialenosti = Array.new($N); vzdialenosti[zaciatok] = 0
  predchadzajuci = Array.new($N)
  navstivene = Array.new($N)
  teraz = nil
  while true
    teraz = najblizsi_nenavstiveny_bod(navstivene, vzdialenosti, zaciatok)
    break if teraz == nil or teraz == koniec
    navstivene[teraz] = true
    ($susedia[teraz] - zakazane).each do |sused|
      if vzdialenosti[sused] == nil or vzdialenosti[teraz]+1 < vzdialenosti[sused]
        vzdialenosti[sused] = vzdialenosti[teraz]+1
        predchadzajuci[sused] = teraz
      end
    end
  end
  return nil if teraz == nil   # nemame cestu...
  cesta = []
  while teraz
    cesta << teraz
    teraz = predchadzajuci[teraz]
  end
  return cesta.reverse
end

def stretli_sa(bod)
  o_ten_bod_potrebuje = (not existuje_cesta($O, $P, $zakazane_body_O + [bod]))
  a_ten_bod_potrebuje = (not existuje_cesta($A, $P, $zakazane_body_A + [bod]))
  if o_ten_bod_potrebuje and a_ten_bod_potrebuje then puts "Nejde to."; exit end
  $zakazane_body_A << bod if o_ten_bod_potrebuje
  $zakazane_body_O << bod if a_ten_bod_potrebuje
end

print "Zadaj N: "; $N = readline.to_i
print "Zadaj O: "; $O = readline.to_i - 1
print "Zadaj P: "; $P = readline.to_i - 1
print "Zadaj A: "; $A = readline.to_i - 1
print "Zadaj M: "; $M = readline.to_i

$M.times{ print "Zadaj a b: "; r = readline.split(" "); pridaj_hranu(r[0].to_i-1, r[1].to_i-1) }

$zakazane_body_O = []
$zakazane_body_A = []

mam_dobru_cestu = false
while not mam_dobru_cestu
  cesta1 = najdi_cestu($O, $P, $zakazane_body_O)
  cesta2 = najdi_cestu($P, $A, $zakazane_body_A)
  cesta1.pop   # $P uz mam v ceste 2
  mam_dobru_cestu = true
  cesta1.each{ |b| if cesta2.member? b then mam_dobru_cestu = false; stretli_sa(b); break end }
end

puts(cesta1.map{|n|n+1}.join(" ") + " " + cesta2.map{|n|n+1}.join(" "))