== include(page="template/taskheader" task_id="tcast") ==
Reteaua de comunicatie a orasului Ploiesti este alcatuita din $N$ noduri, numerotate de la $1$ la $N$. Exista $N-1$ perechi de noduri intre care exista conexiune directa (aceste noduri sunt denumite vecini). O conexiune directa asigura comunicare in ambele sensuri intre nodurile conectate. Conexiunile directe sunt construite astfel incat oricare doua noduri ale retelei pot comunica (direct, sau indirect, prin intermediul altor noduri).

La momentul de timp $0$, nodul $1$ are un mesaj pe care doreste sa il trimita tuturor celorlalte noduri. Pentru aceasta, la orice moment de timp intreg t, orice nod $x$ ( $1 ≤ x ≤ N$ ) care a primit in prealabil mesajul (sau care l-a primit exact la momentul $t$), il poate trimite unui vecin $y$ al sau care nu a primit inca mesajul. Transmisia mesajului dureaza $1$ unitate de timp - asadar, nodul $y$ va primi mesajul la momentul $t+1$. Un nod poate trimite mesajul catre mai multi vecini ai sai, dar nu simultan.
Din motive de securitate, la anumite momente de timp din intervalul [ $0$ , $T$ ), nodurile de comunicatie sunt verificate. Pentru fiecare nod $x$ ( $1 ≤ x ≤ N$ ) si fiecare moment de timp $t$ ( $0 ≤ t ≤ T-1$ ), se cunoaste daca nodul $x$ este verificat sau nu la momentul $t$. Durata verificarii este de $1$ unitate de timp (astfel, daca nodul $x$ este verificat la momentul $t$, verificarea se termina la momentul $t+1$ ). La fiecare moment de timp la care un nod este verificat, acesta nu poate trimite nici un mesaj (dar poate primi mesaje de la vecinii sai).

La momentul de timp $0$, nodul $1$ are un mesaj pe care doreste sa il trimita tuturor celorlalte noduri. Pentru aceasta, la orice moment de timp întreg t, orice nod $x$ ($1 ≤ x ≤ N$) care a primit in prealabil mesajul (sau care l-a primit exact la momentul $t$), il poate trimite unui vecin $y$ al sau care nu a primit încă mesajul. Transmisia mesajului durează $1$ unitate de timp – asadar, nodul $y$ va primi mesajul la momentul $t+1$. Un nod poate trimite mesajul catre mai multi vecini ai sai, dar nu simultan.
Din motive de securitate, la anumite momente de timp din intervalul [ $0$ , $T$ ), nodurile de comunicaÅ£ie sunt verificate. Pentru fiecare nod $x$ ($1 ≤ x ≤ N$) si fiecare moment de timp $t$ ($0 ≤ t ≤ T-1$), se cunoaÅŸte dacă nodul $x$ este verificat sau nu la momentul $t$. Durata verificarii este de $1$ unitate de timp (astfel, daca nodul $x$ este verificat la momentul $t$, verificarea se termină la momentul $t+1$). La fiecare moment de timp la care un nod este verificat, acesta nu poate trimite nici un mesaj (dar poate primi mesaje de la vecinii săi).

Determinati durata de timp minima dupa care mesajul poate ajunge de la nodul $1$ la toate nodurile (in cazul unei strategii optime de distributie a mesajului).

Determinaţi durata de timp minimă după care mesajul poate ajunge de la nodul $1$ la toate nodurile (în cazul unei strategii optime de distribuţie a mesajului).

h2. Date de intrare

Prima linie a fisierului de intrare $tcast.in$ contine $2$ numere intregi, separate printr-un spatiu: $N$ si $T$. Urmatoarele $N-1$ linii contin cate doua numere intregi $x$ si $y$, separate printr-un spatiu, avand semnificatia ca nodurile $x$ si $y$ sunt vecine in cadrul retelei de comunicatie. Urmatoarele $N$ linii contin cate $T$ numere intregi din multimea { $0$, $1$ }. Al t-lea numar ( $1 ≤ t ≤ T$ ) de pe a $i$ -a dintre aceste linii este $1$, daca nodul $i$ este verificat la momentul $t-1$ (si $0$ in caz contrar).

Prima linie a fiÅŸierului de intrare $tcast.in$ conÅ£ine $2$ numere întregi, separate printr-un spaÅ£iu: $N$ ÅŸi $T$. Următoarele $N-1$ linii conÅ£in câte două numere întregi $x$ ÅŸi $y$, separate printr-un spaÅ£iu, având semnificaÅ£ia că nodurile $x$ ÅŸi $y$ sunt vecine în cadrul reÅ£elei de comunicaÅ£ie. Următoarele $N$ linii conÅ£in câte $T$ numere întregi din mulÅ£imea { $0$, $1$ }. Al t-lea număr ($1 ≤ t ≤ T$) de pe a $i$ -a dintre aceste linii este $1$, dacă nodul $i$ este verificat la momentul $t-1$ (ÅŸi $0$ în caz contrar).

h2. Date de iesire

Fisierul de iesire $tcast.out$ va contine o singura linie pe care va fi scrisa durata de timp minima dupa care toate nodurile primesc mesajul, in cazul unei strategii optime de distributie a mesajului.

Fişierul de ieşire $tcast.out$ va conţine o singură linie pe care va fi scrisă durata de timp minimă după care toate nodurile primesc mesajul, în cazul unei strategii optime de distribuţie a mesajului.

h2. Restrictii
* $1 ≤ N ≤ 2000$
* $1 ≤ T ≤ 1000$

* Durata de timp dupa care toate nodurile primesc mesajul poate fi mai mare decat $T$

* Durata de timp după care toate nodurile primesc mesajul poate fi mai mare decât $T$

h2. Exemplu

  0 0 0 1 1
  0 0 0 0 0
  0 0 0 0 0

| 5
|
h3. Explicatie

La momentul $0$ nodul $1$ este verificat si nu poate transmite mesajul nici unui vecin. La momentul $1$, nodul 1 trimite mesajul nodului $4$. La momentul $2$, nodul $1$ trimite mesajul nodului $2$, iar nodul $4$ trimite mesajul nodului $5$. La momentul $3$, nodul $2$ trimite mesajul nodului $3$, iar la momentul $4$ nodul $3$ trimite mesajul nodului $6$. La momentul $5$, nodul $6$ este ultimul nod care primeste mesajul.

La momentul $0$ nodul $1$ este verificat ÅŸi nu poate transmite mesajul nici unui vecin. La momentul $1$, nodul 1 trimite mesajul nodului $4$. La momentul $2$, nodul $1$ trimite mesajul nodului $2$, iar nodul $4$ trimite mesajul nodului $5$. La momentul $3$, nodul $2$ trimite mesajul nodului $3$, iar la momentul $4$ nodul $3$ trimite mesajul nodului $6$. La momentul $5$, nodul $6$ este ultimul nod care primeste mesajul.

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

3086