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

Poveste şi cerinţă...

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.

h2. Date de intrare

Fişierul de intrare $symmetricgraph2.in$ ...

Fişierul de intrare $symmetricgraph2.in$ va conţine pe prima sa linie valorile $N$ şi $M$ reprezentând numărul de noduri, respectiv de muchii ale grafului. Următoarele $M$ linii conţin câte un triplet de numere $X Y C$ cu semnificaţia că există o muchie neorientată de capacitate $C$ între nodurile $X$ şi $Y$.

h2. Date de ieşire

În fişierul de ieşire $symmetricgraph2.out$ ...

În fişierul de ieşire $symmetricgraph2.out$ se va afla o singură valoare, reprezentând cantitatea maximă de flux ce poate fi trimisă prin reţeaua descrisă în fişierul de intrare.

h2. Restricţii

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