== include(page="template/taskheader" task_id="cupaberii") ==
Poveste şi cerinţă...
Gigel incearca sa duca o viata sanatoasa si s-a apucat de alergat, el participa in fiecare an la multe concursuri dar bineinteles cursa lui preferata este Cupa Berii. Cupa berii se desfasoara pe un drum de lungime $N$ Km. Drumul este rectilinu, incepe la pozitia $0$ si se termina la pozitia $N$. Drumul are o banda pe fiecare sens. Exista $M <= 4*N$ marci de bere care sponsorizeaza cursa, fiecare marca va avea o zona in care va oferi bere concurentilor. Pentru fiecare marca se da intervalul $x,y$ in care acea marca ofera bere(daca $x<y$ atunci standul este pe sensul de mers de la stanga la dreapta, altfel standul este pe sensul dreapta stanga). Mai multe standuri se pot suprapune in acelasi interval.
Cupa berii nu este o competitie ca oricare alta, concurentii trebuie sa bea neaparat o bere la fiecare KM in care exista un stand de bere, ei isi pot alege ce fel de bere vor bea daca au mai multe optiuni.
Totusi concurentii nu trebuie sa parcurga musai tot traseul $(0->N->0)$. Ei pot incepe de pe orice pozitie $P1$ (numar natural) si trebuie sa se deplaseze IN DREAPTA catre o alta pozitie $P2 > P1$ (numar natural), parcurgand drumul $P1 -> P2$. Ei sunt obligati sa faca insa si drumul de intors, si anume $P2 -> P1$.
Gigel doreste sa participe la cupa berii dar mai are o cerinta un pic speciala. El vrea sa bea numarul maxim de beri din cel putin un brand de bere si mai doreste sa faca acest lucru ori la inceput traseului(P1->...) ori imediat dupa intoarcere(<-P2). Gigel va cere ajutorul si va intreaba in cate moduri isi poate alege traseul.(Analizati exemplul pt clarificari)
Cupa berii se desfasoara pe $T <= 10$ trasee distincte.
h2. Cerinta
Pentru fiecare din cele $T$ trasee calculati numarul de posibilitati pe care il are Gigel de a-si alege traseul.
h2. Date de intrare
Fişierul de intrare $cupaberii.in$ ...
Prima linie a fişierului $drumuri.in$ conţine numerele $T$, urmeaza $T$ teste.
Fiecare teste incepe cu un rand pe care se afla $N$ şi $M$, cu semnificaţia din enunţ . Următoarele $M$ linii conţin câte trei numere $x_i$, $y_i$.
h2. Date de ieşire
În fişierul de ieşire $cupaberii.out$ ...
Fisierul trebuie sa contina $T$ linii, pe linia $i$ raspunsul pentru al $i-lea$ traseu.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1$ ≤ $T$ ≤ $10$
* $1$ ≤ $N$ ≤ $100.000$
* $1$ ≤ $M$ ≤ $400.000$
* Pentru fiecare stand $x != y$
* Standurile vor fi incluse in totalitate in drum.
* Cupa berii se desfasoara in mod normal pe un circuit si trebuie sa bei o bere la inceputul fiecarei ture de circuit :).
* Cupa berii 2015 nu s-a anuntat inca :)
h2. Exemplu
table(example). |_. cupaberii.in |_. cupaberii.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 2
4 4
1 3
2 4
3 4
4 1
10 1
1 9
| 5
2
|
h3. Explicaţie
Pentru primul traseu Gigel are urmatoarele optiuni:
$0 - 4$ (bea la intoarcere tipul $4$ de bere $4->1$)
$1 - 3$ (bea la dus tipul $1$ de bere)
$1 - 4$ (bea la dus tipul $1$)
$2 - 4$ (bea la dus tipul $2$)
$3 - 4$ (bea la dus tipul $3$)
h3. Pentru al doilea traseu Gigel are 2 optiuni:
$1 - 9$
$1 - 10$ (tipul $1$...)
Gigel nu poate incepe la pozitia $0$ pentru ca trebuie sa bea la inceput toate berile de un tip. El nu poate merge $9 - 0$ pentru ca standul de bere se afla pe sensul stanga dreapta.
...
== include(page="template/taskfooter" task_id="cupaberii") ==
== include(page="template/taskfooter" task_id="cupaberii") ==
