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

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_i,y_i$ in care acea marca ofera bere(daca $x_i<y_i$ 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 se pot deplasa fie in stanga sau in dreapta catre o alta pozitie P2 (numar natural), urmand sa faca de asemenea si drumul intors: P1 -> P2, P2 -> P1.

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.

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 ori imediat dupa intoarcere. Gigel va cere ajutorul si va intreaba in cate moduri isi poate alege traseul.(Analizati exemplul pt clarificari)

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

Cupa berii se desfasoara pe T <= 10 trasee distincte.

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

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

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(tipul 3)
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.

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") ==