| Fişierul intrare/ieşire: | cupaberii.in, cupaberii.out | Sursă | ONIS 2015, Runda 2 |
| Autor | Marius Dumitran | Adăugată de |  Iulia Duta •jul123 |
| Timp execuţie pe test | 1.5 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Cupa Berii
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.
Cerinta
Pentru fiecare din cele T trasee calculati numarul de posibilitati pe care il are Gigel de a-si alege traseul.
Date de intrare
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.
Date de ieşire
Fisierul trebuie sa contina T linii, pe linia i raspunsul pentru al i-lea traseu.
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 :)
Exemplu
| cupaberii.in | cupaberii.out |
|---|---|
| 2 4 4 1 3 2 4 3 4 4 1 10 1 1 9 | 5 2 |
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)
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.
