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

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.

Jocul se joaca alternativ, fiecare trebuie sa aleaga un nod care nu a mai fost ales pana se termina graful.

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

sum(S) + sum(u_i, v_i) daca u_i \in S si v_i \in S. Unde S este multimea nodurilor alese de un jucator.

<tex>sum(S) + sum(u_i, v_i) </tex> daca <tex>u_i \in S </tex> si <tex>v_i \in S \forall i \in [1, N]</tex>. Unde S este multimea nodurilor alese de un jucator.

Care este diferenta dintre scorul lui Alex si a lui Cristinel, daca ambii jucatori joaca optim si Alex incepe primul?
h2. Date de intrare