Паради#7717

Паради

1 секунда

128 мегабайтів

Дуже легка

У місті Вічного Святкування є $n$ перехресть і $n - 1$ n - 1 двонаправлених вулиць, кожна з яких з'єднує два перехрестя. Між будь-якими двома перехрестями існує рівно один шлях, що з'єднує їх безпосередньо або через інші вершини. Жодне перехрестя не має більше $10$ вулиць.

Щороку $13$ вересня ( $256$ -ий день року) в місті відбувається багато фестивалів. Зокрема, жителі хочуть організувати $m$ парадів. Парад номер $i$ починається на перехресті $u_{i}$ u_i і закінчується на $v_{i}$ v_i, слідуючи унікальним шляхом між вершинами.

Як мер міста, ви відповідаєте за безпеку городян. Для цього ви видали указ, що жодним двом парадам не дозволяється використовувати одну і ту ж вулицю, хоча вони можуть мати спільні перехрестя або навіть спільні кінцеві точки.

Щоб заспокоїти своїх громадян, ви намагаєтеся організувати якомога більше парадів, не порушуючи правил безпеки.

Вхідні дані

Перший рядок містить кількість тестів $t$ . Перший рядок кожного тесту містить число перехресть $n$ ( $2 \leq n \leq 1000$ 2 \le n \le 1000). Кожен з наступних $n - 1$ n - 1 рядків містить два цілих числа $a$ , $b$ ( $1 \leq a \neq = b \leq n$ 1 \le a \ne b \le n), що вказують на те, що перехрестя $a$ і $b$ з'єднані вулицею. З кожного перехрестя виходить не більше $10$ вулиць.

Наступний рядок містить кількість запланованих парадів $m$ ( $0 \leq m \leq n \cdot (n - 1) /2$ 0 \le m \le n \cdot (n - 1) / 2). Кожен з наступних $m$ рядків містить два числа $u_{i}$ u_i, $v_{i}$ v_i ( $1 \leq u_{i} \neq = v_{i} \leq n$ 1 \le u_i \ne v_i \le n), що означають, що парад починається на перехресті $u_{i}$ u_i і закінчується на перехресті $v_{i}$ v_i. Жодні два паради не мають спільних кінців.

Вихідні дані

Для кожного тесту виведіть в окремому рядку найбільшу кількість парадів, які можна організувати без використання спільних вулиць.

Приклади

Приклад 1