== include(page="template/taskheader" task_id="sever") ==
Era toamnă. O zi obișnuită de marți avea să devină totuși definitorie pentru proful nostru de matematică, Sever.
Era toamnă. O zi obişnuită de marţi avea să devină totuşi definitorie pentru proful nostru, domnul Blând.
Într-o oră de analiză algebrică a luat naștere un murmur în al cărui crescendo Sever a spus ”îmi testați limitele!”, cu clasicul lui zâmbet dintr-o parte în cealaltă a feței. Dar, în comparație cu alte dăți, era vizibil întristat că elevii nu sunt atenți la oră.
Într-o oră ca oricare alta a luat naştere un murmur în al cărui crescendo d-l. Blând a spus ”îmi testaţi limitele!”, cu clasicul lui zâmbet dintr-o parte în cealaltă a feţei. Dar, în comparaţie cu alte dăţi, era vizibil întristat că elevii nu sunt atenţi la oră.
Sever: ”În mod automat, îmi veți spune ce este atât de interesant.” (se uită către banca Luca, surprinzător de agitată)
MT: ”Un desen animat la care am început să ne uităm” (și-a dat seama că poate Sever nu știe ce e ăla anime)
Sever: ”?”
Blând: ”În mod automat, îmi veţi spune ce este atât de interesant.” (se uită către banca Luca, surprinzător de agitată)
MT: ”Un desen animat la care am început să ne uităm” (şi-a dat seama că poate Blând nu ştie ce e ăla anime)
Blând: ”?”
Perju: ”E vorba despre o fată care vrea să lucreze la o cafenea.”
Sever: ”??”
Blând: ”??”
MT: ”Dar află că de fapt cafenelele sunt clanuri în război unele cu altele”
({_Sever, din ce în ce mai confuz de ce discuția continuă, se uită către Cristi cerând explicații_})
({_Blând, din ce în ce mai confuz de ce discuţia continuă, se uită către Cristi cerând explicaţii_})
Cristi: ”S-au uitat aseară și n-am fost, nu știu ce să zic.”
Cristi: ”S-au uitat aseară şi n-am fost, nu ştiu ce să zic.”
Dintr-odata, Sever îi cere o foaie. Trec 5, 10 minute, timp în care o umple de notații într-o frenezie, după care zice: ”un lucru pe care nu i l-am spus nimănui este că sunt pasionat de doujinshi. Evident, mi-am dat seama că vorbiți despre **redacted**, și nu m-am putut abține să nu fac o problemă la care să vă gândiți. Dacă tot nu sunteți atenți, măcar fetele care vă trec prin cap să vă ajute la ceva. Am dreptate, domnule Marcu? ({_zâmbet_})”
Dintr-odata, d-l. Blând îi cere o foaie. Trec 5, 10 minute, timp în care o umple de notaţii într-o frenezie, după care zice: ”un lucru pe care nu i l-am spus nimănui este că sunt pasionat de doujinshi. Evident, mi-am dat seama că vorbiţi despre **redacted**, şi nu m-am putut abţine să fac o problemă la care să vă gândiţi. Dacă tot nu sunteţi atenţi, măcar fetele care vă trec prin cap să vă ajute la ceva. Am dreptate, domnule Marcu? ({_zâmbet_})”
Nu, problema compusă de Sever n-a fost o geometrie asemănătoare celor din IMO, ci, spre surprinderea întregii clase, una de informatică. Nu știm de ce, dar probabil a intuit că ne-ar prinde niște antrenament înainte de concursul de la Shumen. Problema pe care a enunțat-o pe tablă spune astfel:
Problema pe care a enunţat-o pe tablă spune astfel:
h2. Cerință
h2. Cerinţă
Nagomi este însărcinată cu eliminarea tuturor celorlalte cafenele, în chiar prima ei zi de muncă la Ton Tokoton. Fiindcă celelalte cafenele vor să-și unească forțele, organizează o întâlnire secretă. Cel puțin, așa cred ele. De fapt, Nagomi are harta încăperilor unde va dormi fiecare membru al celorlalte cafenele. Această hartă este reprezentată sub formă de graf conex aciclic.
Nagomi este însărcinată cu eliminarea tuturor celorlalte cafenele, în chiar prima ei zi de muncă la Ton Tokoton. Fiindcă celelalte cafenele vor să-şi unească forţele, organizează o întâlnire secretă. Cel puţin, aşa cred ele. De fapt, Nagomi are harta încăperilor unde va dormi fiecare membru al celorlalte cafenele. Această hartă este reprezentată sub formă de graf conex aciclic.
Nagomi, care a ajuns la o înțelegere cu proprietara hotelului, află că paturile sunt echipate cu ace otrăvite care pot înțepa persoana care doarme fără să o trezească. Ea dobândește un dispozitiv special care are următoarea abilitate: pentru 2 camere $a$ și $b$, activează acele camerelor de pe lanțul dintre $a$ și $b$. Procesul de înțepare efectuat simultan pe toate camerele durează o secundă.
Nagomi, care a ajuns la o înţelegere cu proprietara hotelului, află că paturile sunt echipate cu ace otrăvite care pot înţepa persoana care doarme pe el fără să o trezească. Ea dobândeşte un dispozitiv special care are următoarea abilitate: pentru 2 camere $a$ şi $b$, activează acele camerelor de pe lanţul dintre $a$ şi $b$. Procesul de înţepare efectuat simultan pe toate camerele durează o secundă.
Nagomi stabilește niște activări, poate cu antipatie pe anumite alte servitoare. Se mai știe un lucru: membrii unei cafenele sunt atât de conectați între ei, încât înțeparea unuia îi afectează pe toți. Fiecare cafenea are toleranța ei, adică numărul maxim de înțepături pe care poate să îl suporte fără să fie distrus. Acum Nagomi se întreabă: pentru fiecare clan, care este momentul de timp în care acesta este distrus?
Nagomi stabileşte nişte activări, care vor fi realizate in ordinea data, poate cu antipatie pe anumite alte servitoare. Se mai ştie un lucru: membrii unei cafenele sunt atât de conectaţi între ei, încât înţeparea unuia îi afectează pe toţi. Fiecare cafenea are toleranţa ei, adică numărul maxim de înţepături pe care poate să îl suporte întregul clan fără să fie distrus. Acum Nagomi se întreabă: pentru fiecare clan, care este momentul de timp în care acesta este distrus?
Sever, mândru de faptul că a mai consumat o rezervă de marker, așteaptă răbdător un răspuns riguros.
D-l. Blând, mândru de faptul că a mai consumat o rezervă de marker, aşteaptă răbdător un răspuns riguros.
h2. Date de intrare
Pe prima linie a fişierului de intrare $sever.in$ se afla numerele $N$ și $M$, reprezentând numărul de camere, respectiv numărul de clanuri. Camerele sunt numerotate de la $1$ la $N$. Pe următoarele $N-1$ linii se află câte $2$ numere, $x$ și $y$, cu semnificația că există conexiune între camera $x$ și camera $y$.
Următoarea linie conține $N$ valori, a $i$-a reprezentând clanul femeii din camera $i$.
Următoarea linie conține $M$ valori, a $i$-a reprezentând toleranța clanului $i$.
Pe următoarea linie se află $Q$, numărul de activări ale dispozitivului. Următoarele $Q$ linii conțin $2$ numere $x$ și $y$, ce înseamnă că dispozitivul a fost activat între camerele $x$ și $y$.
Pe prima linie a fişierului de intrare $sever.in$ se afla numerele $N$ şi $M$, reprezentând numărul de camere, respectiv numărul de clanuri. Camerele sunt numerotate de la $1$ la $N$. Pe următoarele $N-1$ linii se află câte $2$ numere, $x$ şi $y$, cu semnificaţia că există conexiune între camera $x$ şi camera $y$.
Următoarea linie conţine $N$ valori, a $i$-a reprezentând clanul femeii din camera $i$.
Următoarea linie conţine $M$ valori, a $i$-a reprezentând toleranţa clanului $i$.
Pe următoarea linie se află $Q$, numărul de activări ale dispozitivului. Următoarele $Q$ linii conţin $2$ numere $x$ şi $y$, ce înseamnă că dispozitivul a fost activat între camerele $x$ şi $y$.
h2. Date de ieşire
În fişierul de ieşire $sever.out$ se vor scrie pe o linie, separate de câte un spațiu, $M$ valori, a $i$-a reprezentând momentul de timp în care clanul $i$ este distrus. Dacă acesta supraviețuiește atacului, se va afișa $-1$
În fişierul de ieşire $sever.out$ se vor scrie pe o linie, separate de câte un spaţiu, $M$ valori, a $i$-a reprezentând momentul de timp în care clanul $i$ este distrus. Dacă acesta supravieţuieşte atacului, se va afişa $-1$
h2. Restricţii
* $1 ≤ N, M, Q ≤ 200 000$
* $1 ≤ N, Q ≤ 200 000$
* $1 ≤ M ≤ N$
* Toleranţele sunt numere întregi nenegative care încap în tipul de date $int$
* Testele problemei sunt grupate după cum urmează:
table(restrictii). |_. # |_. Punctaj |_. Restricţii |
table(restrictii). |_. Subtask |_. Punctaj |_. Restricţii |
| $1$ | $15$ | $N, Q ≤ 5 000$ |
| $2$ | $20$ | $M ≤ 100$ |
| $3$ | $35$ | $N, M, Q ≤ 50 000$|
| $4$ | $30$ | Restricțiile originale |
| $2$ | $20$ | $1 ≤ M ≤ 100$ |
| $3$ | $35$ | $N, Q ≤ 100 000$|
| $4$ | $30$ | Restricţiile originale |
* Enunțul problemei este un pamflet și trebuie tratat ca atare.
* Enunţul problemei este un pamflet şi trebuie tratat ca atare.
h2. Exemplu
