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

Cristinel si Alex au gasit un grafuri cu *N* noduri si *M* muchii. Pe fiecare dintre muchii si noduri era scris un numar natural.
Vazand aceasta capodopera a matematicii discrete, Alex a propus sa se joace un joc pe acel graf.

Cristinel si Alexei au gasit un graf neorientat cu *N* noduri si *M* muchii. Pe fiecare dintre muchii si noduri era scris un numar natural.
Vazand aceasta capodopera a matematicii discrete, Alexei a propus sa se joace un joc pe acel graf.

Jocul se joaca alternativ, fiecare trebuie sa aleaga un nod care nu a mai fost ales, pana se termina graful.
La final, punctajul fiecarui jucator este suma numerelor de pe nodurile alese si a muchiilor
a caror varfuri sunt in multimea nodurilor alese de acel jucator. Formal, scorul unui jucator este
<tex>sum(S) + sum(u_i, v_i) </tex> daca <tex>u_i, v_i \in S </tex> <tex>\forall i \in [1, N]</tex>. Unde *S* este multimea nodurilor alese de un jucator.

Care este diferenta dintre scorurile jucatorilor, daca ambii jucatori joaca optim si Alex incepe primul?

Care este diferenta dintre scorurile jucatorilor, daca ambii jucatori joaca optim si Alexei incepe primul?
Precizare: Joc optim inseamna maximizarea diferentei de scor.

h2. Date de intrare