Мавзӯи интихобӣ

Мартышкаҳо нақша доранд дар ягон зоопарк вохӯранд. Ба онҳо кӯмак кунед, то зоопарке ёбанд, ки талаботи онҳоро қонеъ гардонад. Ба таври расмӣ, лозим аст зоопарки $A$-ро пайдо кунед, ки барои ҳар як мартышкаи $i$ шарти зерин иҷро шавад:

$\text{dist}(a_i, A) + \text{dist}(A, b_i) \leq d_i$

Ё хабар диҳед, ки чунин зоопарк вуҷуд надорад.

Формати Вуруд

• Сатри аввал як адади бутуни $T$ — шумораи тестҳоро дар бар мегирад.

  • Сипас, барои ҳар тест:

    • Сатри аввал ду адади бутуни ҷудошуда бо фосила $N, M$-ро дар бар мегирад.
    • Баъдан $N-1$ сатр меоянд, ки ҳар кадом ду адади бутуни ҷудошуда бо фосила $x_i, y_i \ (1 \leq x_i, y_i \leq N, \ x_i \neq y_i)$ — канори дарахтро тасвир мекунанд.
    • Баъд $M$ сатр меоянд — тавсифи талаботи мартышкаҳо; ҳар сатр се адади бутуни ҷудошуда бо фосила $a_i, b_i, d_i \ (1 \leq a_i, b_i \leq N, \ 0 \leq d_i \leq 1,000,000,000)$ дорад.

Маҳдудиятҳо

• $1 \leq T \leq 1,000$
• $1 \leq N \leq 200,000$
• $1 \leq M \leq 200,000$
• Ҷамъбасти $N$ дар ҳамаи тестҳо аз $200,000$ бештар нест.
• Ҷамъбасти $M$ дар ҳамаи тестҳо аз $200,000$ бештар нест.

Формати Баромад

Барои ҳар тест ҷавобро чоп кунед (агар чанд зоопарк ҷавоби дуруст бошанд, ҳар кадомашро чоп кардан мумкин аст), ё $-1$ агар ҷавоб вуҷуд надошта бошад.

Системаи баҳодиҳӣ

Бигзор $S_N, S_M$ — суммаи умумии $N$ ва $M$ дар ҳамаи тестҳо бошанд.