Haos

Time limit: 2.5s Memory limit: 256MB Input: Output:

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

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

Se dau NN prieteni și MM relații de tipul xi,yi,wix_i, y_i, w_i, ce reprezintă că prietenul cu indicele xix_i îi plătește celui cu indicele yiy_i suma de wiw_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 NN relații care este echivalentă1^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 NN prieteni. Mai exact, se mai dau QQ perechi de prieteni (sau mai bine zis, foști prieteni) ui,viu_i, v_i care nu vor să își transfere bani unul altuia (în plățile finale echivalente, uiu_i nu îi poate plăti lui viv_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-1.

Date de intrare

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

Pe următoarele MM linii se află câte trei numere întregi xi,yi,wix_i, y_i, w_i - reprezentând cele MM relații inițiale.

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

Pe următoarele QQ linii relațiile de dușmănie ăparute în excursie ui,viu_i, v_i.

Date de ieșire

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

Restricții și precizări

  • 1^1Două 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
  • 1N1051 \leq N \leq 10^5;
  • 1M1051 \leq M \leq 10^5;
  • 1xi,yiN1 \leq x_i, y_i \leq N;
  • 1wi1091 \leq w_i \leq 10^9;
  • 0Q1050 \leq Q \leq 10^5;
  • 1ui,viN1 \leq u_i, v_i \leq N.

Punctare

# Punctaj Restricții
0 0 Exemplele
1 30 1n5 0001 \leq n \leq 5 \ 000
2 20 Q=0Q = 0
3 50 Fără alte restricții

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

Log in or sign up to be able to send submissions!