== 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 \in S </tex> si <tex>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 scorul lui Alex si a lui Cristinel, daca ambii jucatori joaca optim si Alex incepe primul?

<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 Alexei incepe primul?
Precizare: Joc optim inseamna maximizarea diferentei de scor.

h2. Date de intrare

h2. Restricţii

* $1 ≤ N, M ≤ 10^5^$
* $1 ≤ Numarul scris pe noduri ≤ 10^5^$
* $1 ≤ Numarul scris pe muchii ≤ 10^5^$

* $0 ≤ N, M ≤ 10^5^$
* $0 ≤ Numarul scris pe noduri ≤ 10^5^$
* $0 ≤ Numarul scris pe muchii ≤ 10^5^$

* $1 ≤ T ≤ 10$
h2. Exemplu

table(example). |_. jocgraf.in |_. jocgraf.out |
| 1
  3 3

  1 1 1

  1 2 1
  2 3 1
  3 1 1

h3. Explicaţie

Pentru toate nodurile si muchiile au costul 1, nu conteaza ce noduri o sa aleaga fiecare, diferenta de scor oricum o sa fie 2.

Pentru ca toate nodurile si muchiile au costul 1, nu conteaza ce noduri o sa aleaga fiecare, diferenta de scor oricum o sa fie 2.

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