dunarea

Dunarea

== include(page="template/taskheader" task_id="dunarea") ==

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 $Xi$ , $Yi$ (1≤ $i$ ≤ $N$ ) şi opresc în toate porturile dintre acestea, $Xi$+1, $Xi$+2 ,..., $Yi$-1,$Yi$. 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$

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

h2. Date de intrare

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 $Xi$ , $Yi$ (1≤ $i$ ≤ $N$ )separate prin câte un spaţiu, reprezentând porturile între care navighează linia de croazieră $i$.

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
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$ ≤ 5000
•	1 ≤ $N$ ≤ 5000
•	1 ≤ $Xi$ ≤ $Yi$ ≤ 5000
•	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$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).

* {$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

h3. Explicaţie

Sunt suficiente 4 abonamente pentru liniile: 2, 8, 4  şi 3.

Sunt suficiente $4$ abonamente pentru liniile: {$2$}, {$8$}, $4$ şi {$3$}.

== include(page="template/taskfooter" task_id="dunarea") ==

3917