ID #123 · Colecția InfoAs · Operatori și expresii

Problema CFR

RAU-Gigel se joacă cu noul său set de cale ferată, primit cadou de ziua lui anul acesta. Setul conține `N` gări distincte din diverse orașe reprezentative ale României (București, Iași, Sebeș, …), numerotate în continuare, pentru simplitate, cu numere de la `1` la `N` și `N - 1` bucăți de șină care pot conecta între ele câte două gări distincte date (conexiunea este bidirecțională) astfel încât folosind aceste șine există un drum unic alcătuit din șine între oricare două gări distincte. Ca orice jucărie, fiecare din cele `N - 1` bucăți de șină are un grad de periculozitate asociat acesteia, o valoare exprimată printr-un număr natural nenul (nimeni nu este perfect până la urmă, nici jucăriile), pentru a ști de la ce vârsta ar fi bine să poată fi folosite de copii, de exemplu. De asemenea, toate bucățile de șină au aceeași lungime constantă, de o unitate. RAU-Gigel își desfășoară joaca pe parcursul a `Q` zile și în fiecare zi este supravegheat de câte un membru al familiei pentru a fi în siguranță. Din nefericire pentru el, în fiecare din cele `Q` zile persoana care îl supraveghează îi încurcă puțin planurile, permițându-i să folosească doar șinele care au gradul de periculozitate cel mult `M` (inclusiv `M`), o valoare naturală nenulă aleasă de aceasta (de remarcat că poate mereu folosi toate gările). Astfel, folosind toate șinele pe care le are la dispoziție pentru a conecta între ele gările corespunzătoare, va obține una sau mai multe așezări conexe maximale de gări (există un drum unic alcătuit din șine între oricare două gări distincte dintr-o așezare) pe care le va numi în continuare orașe. În fiecare astfel de zi, personajul nostru principal primește de la persoana care îl supraveghează un număr natural nenul `K` de bucăți de șină considerate perfect sigure pentru joaca copilului de către respectivul supraveghetor, cu care poate conecta oricare două gări distincte dorește. De asemenea, șinele primite îi sunt luate la finalul zilei (poate că persoana respectivă mai supraveghează și alți copii în următoarele zile și mai are nevoie de ele). RAU-Gigel consideră că un lanț este un șir de una sau mai multe gări distincte astfel încât oricare două gări adiacente din acesta sunt conectate de exact o șină, iar lanțul de lungime maximă este cel format dintr-un număr maxim de bucăți de șină (astfel, lungimea unui lanț este dată de numărul de bucăți de șină din care este alcătuit). Scopul acestuia este ca în fiecare zi să formeze un singur lanț cât mai lung având la dispoziție șinele primite de la supraveghetor și cel mult câte un lanț din fiecare oraș creat de acesta, la alegere (adică pentru fiecare oraș poate să aleagă exact un lanț din el (oricare dorește) sau să nu folosească niciun lanț din acel oraș). ## Cerință RAU-Gigel cunoaște deja toate detaliile a `T` astfel de scenarii de joacă independente și vrea pentru fiecare dintre acestea, pe baza informațiilor date, să-l ajutați să afle în fiecare zi care este lungimea maximă a unui lanț de șine pe care îl poate obține în modul descris anterior (prima cerință), respectiv numărul de modalități distincte de obținere a acestui maxim (a doua cerință), calculat modulo `1.000.000.007`. Două modalități de obținere a maximului sunt considerate distincte dacă cele două submulțimi de orașe din care acesta a selectat lanțurile de lungime maximă sunt diferite. ## Date de intrare Fișierul de intrare `cfr.in` conține pe prima linie un număr natural nenul `T`, reprezentând numărul de scenarii. Pentru fiecare scenariu pe prima linie se află un număr `C` care reprezintă numărul cerinței care trebuie rezolvată. Pe cea de-a doua linie se află `N`, numărul de gări, urmat de `N - 1` linii care reprezintă descrierile șinelor de tren: câte `3` numere `u<sub>i</sub> v<sub>i</sub> w<sub>i</sub>` pe fiecare linie, care reprezintă gările conectate, respectiv gradul de periculozitate pentru bucata de șină cu numărul `i`, `1 ≤ i < N`. Pe următoarea linie se află numărul `Q` urmat de descrierile celor `Q` zile de joacă: câte `2` numere `M<sub>i</sub> K<sub>i</sub>` pe fiecare linie, având semnificațiile din enunț, `1 ≤ i ≤ Q`. ## Date de ieșire Fișierul de ieșire `cfr.out` va conține răspunsurile, în ordinea solicitării, adică lungimea maximă care poate fi obținută în condițiile zilei corespunzătoare dacă `C = 1` sau numărul de modalități distincte de a obține această lungime maximă modulo `1.000.000.007`, dacă `C = 2`. ## Restricții și precizări * `1 ≤ T ≤ 3` * `1 ≤ C ≤ 2` * `1 ≤ N, Q ≤ 100.000` * `1 ≤ u<sub>i</sub>, v<sub>i</sub> ≤ N` * `1 ≤ w<sub>i</sub>, M<sub>i</sub> ≤ 1.000.000.000` * `1 ≤ K<sub>i</sub> ≤ N` * Un lanț poate fi format dintr-o singură gară sau să aibă la cele `2` capete ale sale câte o gară * Nu este obligatoriu ca într-o zi să se folosească toate cele `K<sub>i</sub>` șine primite (mai ales că acest lucru s-ar putea să fie imposibil, pentru că o bucată de șină primită trebuie să conecteze exact două gări distincte într-un lanț)