Fişierul intrare/ieşire:	easygraph.in, easygraph.out	Sursă	ONIS 2014, Runda 1
Autor	Teodor Plop	Adăugată de	FMI No Stress •fmins123
Timp execuţie pe test	0.3 sec	Limită de memorie	12288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Easygraph

După cum spune şi numele problemei, aceasta este o problemă simplă cu grafuri. Iar cu ocazia sărbătorilor de iarnă, Moş Crăciun s-a gândit să scurteze enunţul acestei probleme şi să vă premieze cu 100 puncte dacă o rezolvaţi corect!

Se dă un graf orientat aciclic cu N noduri şi M muchii. Fiecare nod i are o valoare v[i]. Să se găsească şi să se afişeze suma maximă a unui lanţ din graf. Suma unui lanţ este suma valorilor nodurilor conţinute de acesta.

Date de intrare

Fişierul de intrare easygraph.in conţine pe prima linie numărul de teste, T. În continuare, pentru fiecare test, se vor găsi pe prima linie două numere naturale N şi M, având semnificaţia din enunţ. Pe cea de-a doua linie, se vor găsi N numere întregi, elementele vectorului v[i]. Pe următoarele M linii se vor găsi câte două numere x şi y, cu semnificaţia că există un arc de la nodul x la nodul y.

Date de ieşire

În fişierul de ieşire easygraph.out se vor găsi T linii, pe linia i găsindu-se răspunsul pentru testul i.

Restricţii

• T = 20
• 1 ≤ N ≤ 15.000
• 1 ≤ M ≤ 30.000
• -10⁶ ≤ v[i] ≤ 10⁶
• Pot exista mai multe arce între aceleaşi noduri X şi Y.
• Lanţul găsit de sumă maximă trebuie să conţină cel puţin 1 nod.

Exemplu

Explicaţie

Lanţul de sumă maximă este: 3 -> 2 -> 4. Suma lanţului este 19.

Cum se trimit solutii?