Pagini recente » cbinteractiv | Maxim2 | Istoria paginii blog/numbers-everyone-should-know | minmaxtree | funnygraph

Fişierul intrare/ieşire:	funnygraph.in, funnygraph.out	Sursă	IIOT 2019-20 Runda 1
Autor	Tulba-Lecu Gabriel	Adăugată de	Comisia IIOT 2019-20 •unibucPoli2019
Timp execuţie pe test	1.5 sec	Limită de memorie	512000 kbytes
Scorul tău	N/A	Dificultate	N/A

Funnygraph

Ţara Bugland este formată din N oraşe. Fiind o ţară nouă, cele N oraşe nu sunt unite de niciun drum, astfel, guvernul a decis să pornească un proiect care va dura exact M zile şi care are ca scop crearea unei reţele de drumuri între cele N oraşe.

În fiecare zi a proiectului muncitorii din Bugland construiesc două drumuri noi unidirecţionale, un drum de la oraşul x la oraşul y cu cost z şi un alt drum de la oraşul y la oraşul x cu cost -z.

După fiecare zi, locuitorii din Bugland îşi pun următoarea întrebare: există o modalitate de a numerota oraşele astfel încât dacă există o muchie de la oraşul x la oraşul y, costul muchiei să fie C_x-C_y, unde C_i este numărul atribuit oraşului i?

Date de intrare

Din funnygraph.in se vor citi de pe prima linie două numere N şi M, numărul de oraşe respectiv durata proiectului.
Pe următoarele M linii se găsesc câte trei numere x, y, z reprezentând drumurile construite în fiecare zi.

Date de ieşire

În funnygraph.in se vor găsi M linii, pe linia i fiind YEP :) dacă există o modalitate de a numerota oraşele, sau NOPE :/ în caz contrar.

Restricţii

$1 \leq N \leq 5 \cdot 10^4$
$1 \leq M \leq 10^5$
$-10^9 \leq z_i \leq 10^9\ \forall\ 1 \leq i \leq M$
$0 \leq x_i, y_i \leq N - 1\ \forall\ 1 \leq i \leq M$
Pentru teste in valoare de 30 de puncte, $1 \leq N \leq 10^3$ ; $1 \leq M \leq 10^4$
Bugland poate avea drumuri multiple între două oraşe sau chiar drumuri de la un oraş la el însuşi.