Laiko ribojimas: 1s

Atminties ribojimas: 16MB

Duomenų failas: ziedai.in

Rezultatų failas: ziedai.out

Jei norite pateikti savo sprendimą - prisijunkite.

Sukabinti žiedai

Tarpusavyje sukabinta n žiedų, sunumeruotų nuo 1 iki n.

Parašykite programą, kuri rastų, kiek daugiausiai žiedų galima pašalinti, kad tarp žiedų a ir b liktų vientisa, be išsišakojimų grandinė.

ziedai

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašytas žiedų skaičius n (1\\len\\le300), žiedų a ir b numeriai bei skaičius k (1\\lek\\le1000). Tolesnėse k eilučių įrašyta po du skaičius: sujungtų žiedų porų numeriai.

Rezultatai

Rezultatą - vieną sveiką skaičių - programa turi išvesti į pirmą ir vienintelę rezultatų failo eilutę.

Pavyzdžiai

Pradiniai duomenys Rezultatai
10 1 10 9
1 2 2 3 3 4 4 5 4 7 5 6 7 8 8 9 9 10
2