Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

E. Маленький Слоник и дерево
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Маленький Слоник очень любит деревья, а особенно корневые.

У него есть дерево, состоящее из n вершин (вершины пронумерованы от 1 до n), с корнем в вершине с номером 1. В каждой вершине дерева хранится некоторый список чисел, который изначально пуст.

Маленький Слоник хочет выполнить m операций. На i-той операции (1 ≤ i ≤ m) он сначала добавляет число i в списки всех вершин поддерева с корнем в вершине с номером ai, а потом добавляет число i в списки всех вершин поддерева с корнем в вершине bi.

После выполнения всех операций, Маленький Слоник для каждой вершины i хочет посчитать число ci — количество целых чисел j (1 ≤ j ≤ n; j ≠ i) таких, что в списках i-той и j-той вершины есть хотя бы одно общее число.

Помогите Маленькому Слонику, посчитайте числа ci за него.

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

В первой строке заданы два целых числа n и m (1 ≤ n, m ≤ 105) — количество вершин дерева и количество операций.

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

Каждая из следующих m строк содержит два целых числа, разделенных пробелом, ai и bi (1 ≤ ai, bi ≤ n, ai ≠ bi), которые обозначают номера вершин в i-той операции.

Гарантируется, что заданный граф являет неориентированным деревом.

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

В единственной строке выведите n целых чисел через пробел — c1, c2, ..., cn.

Примеры
Входные данные
5 1
1 2
1 3
3 5
3 4
2 3
Выходные данные
0 3 3 3 3
Входные данные
11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
2 9
3 6
2 8
Выходные данные
0 6 7 6 0 2 0 5 4 5 5