Tövsiyələr

Şəhər Əbədi Bayramda n kəsişmə və n - 1 ikitərəfli küçə var, hər biri iki kəsişməni birləşdirir. Hər iki kəsişmə arasında onları birbaşa və ya digər zirvələr vasitəsilə birləşdirən dəqiq bir yol var. Heç bir kəsişmədən 10-dan çox küçə çıxmır.

Hər il 13 sentyabrda (256-cı gün) şəhərdə çoxlu festivallar keçirilir. Xüsusilə, vətəndaşlar m parad təşkil etmək istəyirlər. i nömrəli parad u[i] kəsişməsindən başlayır və zirvələr arasında unikal yol ilə v[i] kəsişməsində bitir.

Şəhərin meri olaraq, siz vətəndaşların təhlükəsizliyinə cavabdehsiniz. Bunun üçün siz fərman verdiniz ki, heç bir iki parad eyni küçədən istifadə edə bilməz, baxmayaraq ki, onlar ümumi kəsişmələrə və ya hətta ümumi son nöqtələrə sahib ola bilərlər.

Vətəndaşlarınızı sakitləşdirmək üçün təhlükəsizlik qaydalarını pozmadan mümkün qədər çox parad təşkil etməyə çalışırsınız.

Giriş Məlumatları

Birinci sətir testlərin sayı t-ni ehtiva edir. Hər testin birinci sətiri kəsişmələrin sayı n-i (2 ≤ n ≤ 1000) ehtiva edir. Növbəti n - 1 sətirin hər biri iki tam ədəd a, b (1 ≤ a ≠ b ≤ n) ehtiva edir, bu da kəsişmələrin a və b bir küçə ilə birləşdirildiyini göstərir. Hər kəsişmədən 10-dan çox küçə çıxmır.

Növbəti sətir planlaşdırılan paradların sayı m-i (0 ≤ m ≤ n * (n - 1) / 2) ehtiva edir. Növbəti m sətirin hər biri iki ədəd u[i], v[i] (1 ≤ u[i] ≠ v[i] ≤ n) ehtiva edir, bu da paradın u[i] kəsişməsindən başlayıb v[i] kəsişməsində bitdiyini göstərir. Heç bir iki paradın ümumi sonu yoxdur.

Çıxış Məlumatları

Hər test üçün ayrı sətirdə ümumi küçələrdən istifadə etmədən təşkil edilə biləcək maksimum parad sayını çıxarın.