Эта история происходит в городе BubbleLand. В этом городе есть n домов. В каждом из этих n домов живет мальчик или девочка. В этом городе люди действительно любят числа, и у каждого есть свое любимое число f. Это означает, что мальчик или девочка, живущие в городе в i-м доме, имеют свое любимое число, равное fi.
Дома пронумерованы числами от 1 до n.
Дома соединены n - 1 двунаправленными дорогами, от любого дома возможно добраться до любого другого. Между каждой парой домов есть ровно один путь.
Новое брачное агенство открыло свои офисы в этом странном городе, и жители были восхищены. Они сразу же отправили q запросов в агенство, каждый запрос был в следующем формате:
- a b — спрашивает, сколько есть способов выбрать пару (мальчик и девочка) такую, что они имеют одинаковое любимое число и живут в домах, находящимся на уникальном пути от дома a до дома b.
Помогите брачному агенству ответить на запросы и расширить их бизнес.
Выходные данные
Для каждого из q запросов выведите единственное число — ответ на этот запрос.
Примечание
В первом вопросе на пути от дома 1 до дома 3 потенциальными парами являются (1, 3) и (6, 3).
Во втором вопросе на пути от дома 7 до дома 5 потенциальными парами являются (7, 6), (4, 2) и (4, 5).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
1 0 0 1 0 1 0
9 2 9 2 2 9 9
2 6
1 2
4 2
6 5
3 6
7 4
2
1 3
7 5
|
2
3
|