Aţi încercat vreodată să construiţi teste pentru probleme de 'flux':problema/maxflow? E neplăcut. Prietenul vostru, pe care, pentru a-i păstra anonimitatea, îl vom numi Xdărăscu, v-a sugerat următoarea construcţie: Se ia un arbore neorientat cu rădăcină, $T1$, o copie identică a sa, $T2$, iar fiecare frunză din $T1$ se leagă cu frunza sa *corespunzătoare* din $T2$ printr-o muchie, de-asemenea neorientată. Se pun capacităţi pe muchii după gust. Rădăcina lui $T1$ va fi sursa reţelei de flux, iar rădăcina lui $T2$ va fi destinaţia reţelei.

Totuşi, ăsta nu ar fi un test foarte bun. Ca să-i demonstraţi asta lui Xdărăscu, v-aţi hotărât să scrieţi un algoritm care calculează fluxul maxim într-o astfel de reţea pentru instanţe mult mai mari ale problemei decât ar fi posibil în mod normal.

Totuşi, ăsta nu ar fi un test foarte bun. Ca să-i demonstraţi asta lui Xdărăscu, v-aţi hotărât să scrieţi un algoritm care calculează fluxul maxim într-o astfel de reţea, pentru instanţe mult mai mari ale problemei decât ar fi posibil în mod normal.

h2. Date de intrare