Laiko ribojimas: 1s

Atminties ribojimas: 16MB

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