$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
  kam_pojdeme = [zaciatok]
  teraz = nil
  while true
    teraz = kam_pojdeme.pop
    return false if teraz == nil   # uz sme minuli frontu a stale nic
    ($susedia[teraz] - zakazane).each do |sused|
      return true if sused == koniec
      kam_pojdeme << sused if not navstivene[sused]
      navstivene[sused] = true
    end
  end
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)
  kam_pojdeme = [zaciatok]
  teraz = nil
  while true
    teraz = kam_pojdeme.pop
    break if teraz == koniec
    return nil if teraz == nil   # uz sme minuli frontu a stale nic
    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
        kam_pojdeme << sused if not navstivene[sused]
        predchadzajuci[sused] = teraz
      end
    end
  end
  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)
  if cesta1 == nil or cesta2 == nil then puts "Nejde to."; exit end
  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(" "))