== include(page="template/taskheader" task_id="apm2") ==
Glorioasa Republică Populară va beneficia de un nou sistem de drumuri! Comisia prezidenţială desemnată sa realizeze această glorioasa sarcină a finalizat planul lucrărilor, folosindu-se cu talent de hârtia şi creioanele puse la dispoziţie de Republică pentru fiecare cetăţean. După cum ştie toată lumea, Republica are $N$ mari oraşe, iar acestea vor fi legate de $M$ drumuri bidirecţionale, fiecare astfel de drum având asociat o anumită taxă necesară pentru parcurgerea sa. Fiind dedicaţi omului de rând, membrii comisiei au aflat şi un arbore parţial de cost minim asociat noii reţele de drumuri, sugerând astfel o serie de drumuri ieftine pe care cetăţeanul le poate folosi pentru a călători intre oricare două oraşe ale Republicii.
Glorioasa Republică Populară va beneficia de un nou sistem de drumuri! Comisia prezidenţială desemnată sa realizeze această glorioasă sarcină a finalizat planul lucrărilor, folosindu-se cu talent de hârtia şi creioanele puse la dispoziţie de Republică pentru fiecare cetăţean. După cum ştie toată lumea, Republica are $N$ mari oraşe, iar acestea vor fi legate de $M$ drumuri bidirecţionale, fiecare astfel de drum având asociat o anumită taxă necesară pentru parcurgerea sa. Fiind dedicaţi omului de rând, membrii comisiei au aflat şi un arbore parţial de cost minim asociat noii reţele de drumuri, sugerând astfel o serie de drumuri ieftine pe care cetăţeanul le poate folosi pentru a călători intre oricare două oraşe ale Republicii.
Însă Marele Lider are alte priorităţi. Marele Fiu este un mare fan al emisiunii Top Gear, iar Marele Lider doreşte ca noua reţea de drumuri să-i impresioneze pe realizatorii acesteia, în caz că aceştia vor decide să viziteze ţara noastră. Astfel, Marele Lider desenează $Q$ noi drumuri pe planul reţelei, drumuri care, după înţelepciunea sa, străbat peisaje impresionante. Marele Lider ar dori ca cel puţin unul din aceste drumuri noi desenate să ajungă în construcţia finală. Dornici să îndeplinească dorinţa Luminatului Conducător, membrii comisiei se întreabă acum, pentru fiecare nou drum propus, care este cea mai mare taxă posibila pe care o pot asocia drumului respectiv astfel încât acesta să apară sigur în arborele parţial de cost minim al Republicii.
Însă Marele Lider are alte priorităţi. Marele Fiu este un mare fan al emisiunii Top Gear, iar Marele Lider doreşte ca noua reţea de drumuri să-i impresioneze pe realizatorii acesteia, în caz că aceştia vor decide să viziteze ţara noastră. Astfel, Marele Lider desenează $Q$ noi drumuri pe planul reţelei, drumuri care, după înţelepciunea sa, străbat peisaje impresionante. Marele Lider ar dori ca unul din aceste drumuri noi desenate să ajungă în construcţia finală. Dornici să îndeplinească dorinţa Luminatului Conducător, membrii comisiei se întreabă acum, pentru fiecare nou drum propus, care este cea mai mare taxă posibila pe care o pot asocia drumului respectiv astfel încât acesta să apară sigur în arborele parţial de cost minim al Republicii.
h2. Date de intrare
Prima linie a fişierului de intrare $apm2.in$ va conţine pe prima sa linie cele trei numere $N$, $M$, si $Q$.
Fiecare dintre următoarele $M$ linii va descrie câte un drum prin trei numere întregi: $X$, $Y$, cele două oraşe legate de drumul respectiv şi $T$, taxa asociată acestuia.
Fiecare dintre următoarele $Q$ linii va descrie câte un drum adăugat de Marele Lider, prin două numere, $A$ şi $B$ reprezentând cele două oraşe legate de drumul respectiv.
Fisierul de intrare $apm2.in$ va conţine pe prima sa linie cele trei numere $N$, $M$, şi $Q$. Fiecare dintre următoarele $M$ linii va descrie câte un drum prin trei numere întregi: $X$, $Y$, cele două oraşe legate de drumul respectiv şi $T$, taxa asociată acestuia. Fiecare dintre următoarele $Q$ linii va descrie câte un drum adăugat de Marele Lider, prin două numere, $A$ şi $B$ reprezentând cele două oraşe legate de drumul respectiv.
h2. Date de ieşire
Fişierul de ieşire $apm2.out$ va conţine Q linii. Pe a $i$-a linie se va afla răspunsul întrebarea $'Care este cea mai mare taxă pe care o putem asocia celei de a $i$-a muchii ipotetice astfel incât aceasta să se afle sigur în arborele parţial de cost minim al reţelei'$.
Fişierul de ieşire $apm2.out$ va conţine Q linii. Pe a $i$-a linie se va afla răspunsul întrebarea $'Care este cea mai mare taxă pe care o putem asocia celei de a $i$-a muchii ipotetice astfel încât aceasta să se afle sigur în arborele parţial de cost minim al reţelei?'$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 10.000$
* $1 ≤ M ≤ 100.000$
* $1 ≤ Q ≤ 1.000$
* Taxele sunt numere naturale din intervalul $[1, 10000]$.
* Se consideră că un drum apare **$sigur$** în APM, dacă acesta apare în toate APM-urile posibile.
* Cele Q întrebări sunt independente unele de altele. Cu alte cuvinte, răspunsul pentru un anumit drum se calculează presupunând ca acesta este singurul drum adăugat celorlalte $M$ deja existente.
* Se garantează că se poate călători între oricare două oraşe folosind cele $M$ drumuri iniţiale ale planului.
h2. Exemplu
table(example). |_. apm2.in |_. apm2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4 3 2
1 2 7
1 3 2
1 4 1
2 3
3 4
| 6
1
|
h3. Explicaţie
...
Dacă drumul între oraşele 2 şi 3 are taxa 6, suntem siguri că acesta se va afla în toţi arborii parţiali de cost minim posibili.
Dacă am fi ales taxa egală cu 7, ar fi existat cel puţin un arbore care nu conţine acest drum: $(1 2)$, $(1 3)$, $(1 4)$.
== include(page="template/taskfooter" task_id="apm2") ==
