Laiko ribojimas: 2s

Atminties ribojimas: 64MB

Jei norite pateikti savo sprendimą - prisijunkite.

Kelio paieška

Jums duotas jungus grafas, sudarytas iš n (1\\leqn\\leq10^5) viršūnių ir m (n-1\\leqm\\leq2*10^5) briaunų. Taip pat jums duotos dvi viršūnės su indeksais a ir b (a\\neqb). Suraskite trumpiausią kelią tarp šių viršūnių.

Įvestis

Pirmoje eilutėje pateikti keturi tarpais atskirti skaičiai n, m, a ir b. Kitose m eilučių pateikta po 2 skaičius a_i ir b_i. Tai reiškia, jog tarp a_i ir b_i viršūnių grafe yra briauna.

Rezultatai

Pirmoje eilutėje išveskite skaičių k: trumpiausiame kelyje tarp a ir b esančių viršūnių skaičių. Antroje eilutėje išveskite k skaičių c_1,c_2,...,c_{k-1},c_{k} - indeksus tų viršūnių, kurios yra kelyje nuo a iki b. Čia c_1=a ir c_k=b ir tarp a_i ir a_{i+1} (1\\leqi\\leqm-1) grafe yra briauna. Jei yra keli galimi trumpiausi keliai, išveskite bet kurį.

Pavyzdžiai

Duomenys Rezultatai Paaiškinimas 
5 5 3 2
3 4
2 4
2 5
1 4
3 5
 
3
3 4 2

Taip pat galimas kelias: 3 5 2