Sim-4-2 | Haos

Vrei să faci ,,buffer overflow'' sau să ,,refulezi tamponul''?

După ce s-au întors din vacanță, $N$ prieteni trebuie să refuleze între ei datoriile acumulate de-a lungul concediului.

Se dau $N$ prieteni și $M$ relații de tipul $x_i, y_i, w_i$, ce reprezintă că prietenul cu indicele $x_i$ îi plătește celui cu indicele $y_i$ suma de $w_i$ Vbucks (cea mai stabilă monedă la momentul actual). Din cauză că multe astfel de plăți sunt redundante, găsiți o altă mulțime de maxim $N$ relații care este echivalentă$^1$ cu cea originală.

Problema ar fi simplă dacă ne-am opri aici, dar din păcate, după o excursie, au apărut anumite relații de dușmănie între cei $N$ prieteni. Mai exact, se mai dau $Q$ perechi de prieteni (sau mai bine zis, foști prieteni) $u_i, v_i$ care nu vor să își transfere bani unul altuia (în plățile finale echivalente, $u_i$ nu îi poate plăti lui $v_i$ și nici vice-versa).

Totuși, este posibil să nu existe nicio mulțime de relații care să satisfacă și echivalența cu cele inițiale, și restricțiile impuse de relațiile de dușmanie. Dacă acesta este cazul, afișați $-1$.

Date de intrare

Pe prima linie se află două numere întregi $N$ și $M$ - numărul de prieteni și numărul de relații.

Pe următoarele $M$ linii se află câte trei numere întregi $x_i, y_i, w_i$ - reprezentând cele $M$ relații inițiale.

Pe următoarea linie se află un singur $Q$ - numărul de relații de dușmănie.

Pe următoarele $Q$ linii relațiile de dușmănie ăparute în excursie $u_i, v_i$.

Date de ieșire

Dacă nu există soluție care să satisfacă enunțul, pe prima linie afișați $-1$. Altfel, pe prima linie veti afisa numarul de tranzactii finale $K$, unde $K \le N$, iar pe urmatoarele $K$ linii se vor afla afla platile.

Restricții și precizări

• $^1$Două mulțimi de relații se consideră echivalente dacă după ce s-ar achita toate plățile, fiecare prieten ar pierde / câștiga la fel de mulți bani
• $1 \leq N \leq 10^5$;
• $1 \leq M \leq 10^5$;
• $1 \leq x_i, y_i \leq N$;
• $1 \leq w_i \leq 10^9$;
• $0 \leq Q \leq 10^5$;
• $1 \leq u_i, v_i \leq N$.

Punctare

Exemplul 1

stdin

6 6
4 5 34
1 3 98
1 2 41
2 3 20
5 6 35
4 6 37
11
2 4
3 4
5 6
1 4
1 2
2 6
3 6
3 5
1 6
2 5
1 5

stdout

4
3 2 21
1 3 139
5 4 1
4 6 72

Exemplul 2

stdin

5 8
1 3 38
2 5 9
1 2 21
4 5 76
3 5 12
1 5 48
2 3 43
1 4 46
7
3 5
1 5
2 4
1 3
2 5
1 4
1 2

stdout

-1