arbore

Să considerăm un arbore cu N vârfuri, numerotate de la 1 la N.

Cerinţă

Scrieţi un program care să adauge, dacă este posibil, un număr minim de muchii astfel încât fiecare vârf (terminal sau nu) să aparţină exact unui singur ciclu.

Date de intrare

Fişierul de intrare arbore.in conţine pe prima linie T, numărul de scenarii. Pentru fiecare scenariu conține pe prima linie N - numărul de vârfuri din arbore, iar pe următoarele N-1 linii $x_{i} \;y_{i}$ - extremităţile muchiei i.

Date de ieşire

Fişierul de ieşire arbore.out va conţine pentru fiecare scenariu pe prima linie valoarea –1 dacă problema nu admite soluţie, respectiv numărul de muchii adăugate, dacă problema admite soluţie. Dacă problema admite soluţie, pe fiecare dintre următoarele linii se vor scrie extremităţile unei muchii adăugate, separate printr-un spaţiu, sub forma $a_{i} \;b_{i}$:

Restricţii

• $3 ≤ S_N ≤ 100 \;000$, unde $S_N$ este suma valorilor N pentru toate scenariile
• 3 ≤ N ≤ 100 000
• $x_i, y_i$ sunt numere întregi din intervalul [1,N].
• Problema a fost modificată

Exemplu

arbore.in

2
4
1 2
2 3
2 4
7
1 2
1 3
3 5
3 4
5 6
5 7	

arbore.out

-1
2
6 7
4 2