magnify

Sukabinti žiedai

Pradinių duomenų failas:
ziedai.in  
Rezultatų failas:
ziedai.out  
Laiko apribojimas:
1 s.  
Atminties apribojimas:
16 Mb.  

Užduotis

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ė.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašytas žiedų skaičius n (1 <= n <= 300), žiedų a ir b numeriai bei skaičius k (1 <= k <= 1000). 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
© Bronė Narkevičienė