시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 1024 MB1510861.538%

문제

Правительство небольшого города Мухоловска решило улучшить транспортную ситуацию в своем городе. Для этого была построена сеть трамвайных путей, соединяющая $n$ трамвайных остановок. Для удобства пассажиров между каждой парой остановок можно было проехать на трамвае. C другой стороны, в целях экономии, проехать между двумя остановками можно было единственным образом. Формально говоря, трамвайная сеть представляет собой дерево с $n$ вершинами. При этом вершины дерева соответствуют остановкам, а ребра --- путям.

Изначально по каждому трамвайному пути проходил хотя бы один трамвайный маршрут. Однако со временем некоторые маршруты оказались отменены, а, следовательно, и некоторые трамвайные пути стали невостребованными. Путь считается невостребованным, если ни один трамвайный маршрут по нему не проходит. С целью экономии средств невостребованные трамвайные пути Мухоловска было решено разобрать.

Ваша задача --- написать программу для определения числа невостребованных путей.

입력

Первая строка входного файла содержит единственное число $n$ --- количество трамвайных остановок города ($2 \le n \le 100000$). Каждая из следующих ($n - 1$)-ой строки содержит описание одного трамвайного пути (ребра дерева). Описание состоит из двух чисел $b$ и $e$ --- номеров остановок, соединенных соответствующим путем. Остановки пронумерованы целыми числами от $1$ до $n$.

В следующей строке содержится число $m$ --- количество трамвайных маршрутов ($0 \le m \le 100000$). В каждой из следующих $m$ строк содержится описание трамвайного маршрута. Описание состоит из двух чисел $x$ и $y$ --- трамвайный маршрут имеет конечные остановки с номерами $x$ и $y$ и проходит по кратчайшему пути между ними ($x \ne y$).

출력

В выходной файл выведите количество невостребованных трамвайных путей Мухоловска.

예제 입력 1

4
1 2
1 3
1 4
0

예제 출력 1

3

예제 입력 2

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

예제 출력 2

1

노트

Иллюстрация ко второму примеру.

Пунктирной линией обозначен невостребованный путь.