Programul de reabilitare turistică 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 () şi opresc în toate porturile dintre acestea, . Un pescar gălăţean se deplasează zilnic din portul în portul 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 la . 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 la .
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 la .
Date de intrare
Fişierul de intrare dunarea.in conţine pe prima linie trei numere naturale nenule şi separate prin câte un spaţiu. şi reprezintă porturile între care se deplasează zilnic pescarul. este numărul de linii de croazieră.
Pe următoarele linii se află câte numere naturale nenule () separate prin câte un spaţiu, reprezentând porturile între care navighează linia de croazieră .
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
Restricții și precizări
- 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 la .
- 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 şi ).
Exemplu
dunarea.in
1 10 8
5 8
1 2
5 10
3 7
3 6
3 4
5 8
2 4
dunarea.out
4
Explicație
Sunt suficiente abonamente pentru liniile: , , şi