Reţeaua de comunicaţie a oraşului Ploieşti este alcatuită din N noduri, numerotate de la 1 la N. Există N-1 perechi de noduri între care există conexiune directă (aceste noduri sunt denumite vecini). O conexiune directă asigură comunicare în ambele sensuri între nodurile conectate. Conexiunile directe sunt construite astfel încât oricare două noduri ale reţelei pot comunica (direct, sau indirect, prin intermediul altor noduri).
La momentul de timp 0, nodul 1 are un mesaj pe care doreşte să îl trimită tuturor celorlalte noduri. Pentru aceasta, la orice moment de timp întreg t, orice nod x (1≤x≤N) care a primit în prealabil mesajul (sau care l-a primit exact la momentul t), îl poate trimite unui vecin y al său care nu a primit încă mesajul. Transmisia mesajului durează 1 unitate de timp – aşadar, nodul y va primi mesajul la momentul t+1. Un nod poate trimite mesajul către mai mulţi vecini ai săi, 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) şi fiecare moment de timp t (0≤t≤T-1), se cunoaşte dacă nodul x este verificat sau nu la momentul t. Durata verificării este de 1 unitate de timp (astfel, dacă 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).

Cerinţă

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).

Date de intrare

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).

Date de ieşire

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.

Restricţii

1 ≤ N ≤ 2000
1 ≤ T ≤ 1000
Durata de timp după care toate nodurile primesc mesajul poate fi mai mare decât T

Exemple

tcast.in	tcast.out	Explicaţii
6 5 1 2 2 3 3 6 1 4 4 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0	5	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.

autor: Mugurel Ionuţ Andreica

propunător: Prof. Emanuela Cerchez

Liceul de Informatica ″Grigore Moisil″

emanuela.cerchez@gmail.com