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

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.

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

h2. Restricţii şi precizări

* $1 ≤ N ≤ 100.000$

* $4 ≤ N ≤ 100.000$

* Capacitatea unei muchii este un număr natural în intervalul $[1, 10^9^]$.

* Pentru $40%$ din punctaj, $N ≤ 1000$

* Pentru $40%$ din punctaj, $N ≤ 2.000$

* Sursa reţelei descrise în input este nodul $1$, iar destinaţia este nodul $N$. Se garantează că graful a fost construit după metoda descrisă în enunţ.

* Rădăcina nu este luată în calcul ca frunză, deşi poate avea gradul egal cu $1$.

h2. Exemplu