C. Дураки и дороги
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Как известно, в Берляндии ровно две проблемы — дураки и дороги. Кроме того, в Берляндии есть n городов, в которых эти дураки живут, а дороги, соответственно, эти города соединяют. Все берляндские дороги двунаправленные. Так как в Берляндии дураков много, то для каждой пары городов есть путь между ними (иначе дураки расстроятся), а также между каждой парой городов есть не более одного простого пути (иначе дураки заблудятся).

Но это еще не все особенности Берляндии. В этой стране дураки иногда ходят друг к другу в гости, и от этого дороги портятся. Дураки не очень умны, поэтому всегда ходят только по простым путям.

Простой путь — это путь, который проходит через каждый город Берляндии не более одного раза.

Правительству Берляндии известны пути, по которым ходят дураки. Помогите правительству для каждой дороги посчитать, сколько различных дураков может по ней проходить.

Обратите внимание на то, как заданы пути дураков во входных данных.

Входные данные

В первой строке записано единственное целое число n (2 ≤ n ≤ 105) — количество городов.

В следующих n - 1 строках записаны по два целых числа через пробел ui, vi (1 ≤ ui, vi ≤ n, ui ≠ vi), означающих, что есть дорога, соединяющая города ui и vi.

В следующей строке записано целое число k (0 ≤ k ≤ 105) — количество пар дураков, которые ходят друг к другу в гости.

В следующих k строках заданы по два целых числа через пробел. В i-й строке (i > 0) записаны числа ai, bi (1 ≤ ai, bi ≤ n). Это означает, что дурак под номером 2i - 1 живет в городе ai и ходит в гости к дураку под номером 2i, который живет в городе bi. Заданные пары городов описывают простые пути, так как между любой парой городов существует ровно один простой путь.

Выходные данные

Выведите n - 1 целое число. Числа должны быть разделены пробелами. i-e число должно быть равно количеству дураков, которые могут проходить по i-той дороге. Дороги нумеруются с единицы в порядке их следования во входных данных.

Примеры
Входные данные
5
1 2
1 3
2 4
2 5
2
1 4
3 5
Выходные данные
2 1 1 1
Входные данные
5
3 4
4 5
1 4
2 4
3
2 3
1 3
3 5
Выходные данные
3 1 1 1
Примечание

В первом примере дурак номер 1 пройдет через первую и третью дорогу, а дурак номер 3 — через вторую, первую и четвертую.

Во втором примере через первую дорогу пройдут дураки под номерами 1, 3 и 5, через вторую — дурак номер 5, через третью — дурак номер 3, через четвертую — дурак номер 1.