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

Poveste şi cerinţă...

Bluff a gasit de aceasta data un graf neorientat cu $N$ noduri si $M$ muchii, fiecare avand o valoare asociata. Ea isi pune $Q$ intrebari de forma $(nod,k)$ si vrea sa afle pentru fiecare dintre acestea urmatorul raspuns: care este valoarea maxima $VAL$ astfel incat considerand doar muchiile cu valoare >= $VAL$ sa existe un arbore inclus in graf care sa contina cel putin $k$ noduri, printre care si nodul $nod$.

h2. Date de intrare

Fişierul de intrare $luff.in$ ...

Fişierul de intrare $luff.in$ va contine pe prima linie trei numere, $N,M,Q$ cu semnificatia din enunt. Urmatoarele $M$ linii vor contine cate trei numere intregi $X{~i~},Y{~i~},D{~i~}$ cu semnificatia ca in graf exista o muchie bidirectionala intre nodurile X{~i~} si Y{~i~}, avand valoarea D{~i~}. Urmeaza $Q$ linii, fiecare continand descrierea unui query: $nod{~i~},k{~i~}$.

h2. Date de ieşire

În fişierul de ieşire $luff.out$ ...

În fişierul de ieşire $luff.out$ vor fi afisate $Q$ linii, reprezentand raspunsul la cate o intrebare, in ordinea aparitiei lor in fisierul de intrare. Daca pentru un query nu exista solutie, se va afisa $-1$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $N ≤ 200.000$
* $M ≤ 200.000$
* $Q ≤ 100.000$
* $1 ≤ X{~i~},Y{~i~},nod{~i~} ≤ N$
* $2 ≤ k{~i~} ≤ N$
* $1 ≤ D{~i~} ≤ 1.000.000.000$

h2. Exemplu
table(example). |_. luff.in |_. luff.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 7 7 3
  1 2 12
  2 3 15
  3 4 11
  4 5 12
  5 7 8
  6 7 7
  5 6 4
  2 5
  7 2
  4 3
| 11
  8
  11
|

h3. Explicaţie
 
...
 
== include(page="template/taskfooter" task_id="luff") ==
 

== include(page="template/taskfooter" task_id="luff") ==

8788