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