== include(page="template/taskheader" task_id="dunarea") ==
Poveste şi cerinţă...
Programul de reabilitare turistica a Dunării şi atragere a turiştilor a determinat autorităţile să decidă vânzarea de abonamente pe fiecare linie de croazieră existentă între porturile dunărene, la acelaşi preţ. Vasele unei linii de croazieră navighează între două porturi {$X{~i~}$}, $Y{~i~}$ (1≤ $i$ ≤ $N$ ) şi opresc în toate porturile dintre acestea, {$X{~i~}+1$}, {$X{~i~}+2$},..., {$Y{~i~}-1$}, {$Y{~i~}$}. Un pescar gălăţean se deplasează zilnic din portul $A$ în portul $B$ folosind liniile de croazieră şi ar vrea să reducă cheltuielile cât mai mult. El a ajuns la concluzia că un număr de abonamente pe câte o linie de croazieră, alese eficient, este mai avantajos decât cumpărarea câte unui bilet pentru fiecare călătorie. Din păcate există mai multe combinaţii de linii de croazieră care parcurg traseul de la $A$ la $B$. Pescar fiind, matematica nu este punctul său forte, deci vă cere ajutorul pentru a stabili care este numărul minim de abonamente necesare pentru a ajunge din portul $A$ la $B$
h2. Cerinţă
Scrieţi un program care, pe baza traseelor liniilor de croazieră, să calculeze şi să afişeze numărul minim de abonamente necesare pentru a ajunge de la $A$ la $B$.
h2. Date de intrare
Fişierul de intrare $dunarea.in$ ...
Fişierul de intrare $dunarea.in$ conţine pe prima linie trei numere naturale nenule {$A$}, $B$ şi $N$ separate prin câte un spaţiu. $A$ şi $B$ reprezintă porturile între care se deplasează zilnic pescarul. $N$ este numărul de linii de croazieră.
Pe următoarele $N$ linii se află câte $2$ numere naturale nenule {$X{~i~}$}, {$Y{~i~}$} ({$1 ≤ i ≤ N$})separate prin câte un spaţiu, reprezentând porturile între care navighează linia de croazieră {$i$}.
h2. Date de ieşire
În fişierul de ieşire $dunarea.out$ ...
Fişierul de ieşire $dunarea.out$ va conţine un singur număr natural nenul, reprezentând numărul minim de abonamente necesare.
h2. Restricţii
* $... ≤ ... ≤ ...$
* {$1 ≤ A < B ≤ 5.000$}
* {$1 ≤ N ≤ 5.000$}
* {$1 ≤ X{~i~} ≤ Y{~i~} ≤ 5.000$}
* Se garantează pentru fiecare set de date de intrare existenţa a cel puţin unei linii de croazieră care acoperă întreg traseul de la $A$ la $B$.
* Pot să existe două sau mai multe linii de croazieră între aceleaşi porturi (cum se întâmplă în exemplul de mai jos cu liniile $1$ şi {$7$}).
h2. Exemplu
table(example). |_. dunarea.in |_. dunarea.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1 10 8
5 8
1 2
5 10
3 7
3 6
3 4
5 8
2 4
| 4
|
h3. Explicaţie
...
Sunt suficiente $4$ abonamente pentru liniile: {$2$}, {$8$}, $4$ şi {$3$}.
== include(page="template/taskfooter" task_id="dunarea") ==
