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

$Această problemă este dedicată celor care aşteaptă metroul cu cea mai mare ardoare: locuitorii din Drumul Taberei.$

_Această problemă este dedicată celor care aşteaptă metroul cu cea mai mare ardoare: locuitorii din Drumul Taberei._

Se dă planul unei reţele de metrou cu $N$ staţii şi $M$ tuneluri bidirecţionale între staţii. Două staţii de metrou se numesc vecine dacă există un tunel între ele în acest plan. Fiecare staţie $i$ are asociat un profit $p{~i~}$ dat.
Henry a fost recent promovat dintr-un post de angajat al departamentului de curăţenie pe postul de project manager al firmei. Deoarece nu există fonduri pentru construirea întregii reţele de metrou, Henry trebuie să aleagă o submulţime de staţii care vor fi construite, astfel încât oricare două staţii alese să nu fie vecine în planul iniţial. Pentru a-şi păstra poziţia în companie, suma profiturilor staţiilor alese în această submulţime trebuie să fie maximă.

h2. Restricţii

* $1 ≤ N ≤ 100000$
* $1 ≤ M ≤ 150000$

* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 150 000$

* $1 ≤ x, y ≤ N$

* $1 ≤ p{~i~} ≤ 10000$, pentru orice i, $1 ≤ i ≤ N.$

* $1 ≤ p{~i~} ≤ 10 000$, pentru orice i, $1 ≤ i ≤ N.$

* Există maximum $15$ staţii care se învecinează cu $3$ sau mai multe staţii în planul dat.
* Există maximum $20$ de staţii care se învecinează cu exact o staţie în planul dat.
* Pentru $20%$ din teste, $N ≤ 20$.

table(example). |_. metrou2.in |_. metrou2.out |
| 8 10

1
3
2
5
4
1
2
1

1 3 2 5 4 1 2 1

1 2
2 3
3 4