Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_1998_3e2_ziedai_vyr.in

Rezultatų failas: lmio_1998_3e2_ziedai_vyr.out

Jei norite pateikti savo sprendimą - prisijunkite.

Sukabinti žiedai

Tarpusavyje sukabinta n žiedų. Pavyzdys pateiktas paveiksle.

image

Užduotis

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

Pradiniai duomenys

Pirmoje eilutėje įrašytas žiedų skaičius n, žiedų a ir b numeriai bei skaičius k. Tolesnėse k eilučių įrašyta po du skaičius: sujungtų žiedų porų numeriai.

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

Ribojimai

1\\leqn\\leq300

1\\leqk\\leq1000