У Фермера Джона есть N пастбищ (2 <= N <= 100,000), соединенных N-1 двунаправленными дорогами так, что ровно один путь существует между любыми двумя пастбищами.
Бесси, любимая корова ФД пожаловалась, что на дорогах нет травы, и ФД решил посадить траву на дорогах.
Он делает это, используя процедуру, которая состоит из M шагов. (1 <= M <=100,000).
На каждом шаге происходит одна из двух вещей:
- ФД выбирает два пастбища и высаживает траву на каждой дороге пути между ними - Бесси спрашивает, сколько дорог засажено травой на конкретном пути, и ФД должен ей ответить.
Помогите ФД отвечать на вопросы.
PROBLEM NAME: grassplant
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа N и M
* Строки 2..N: Два разделенных пробелом целых числа, описывающих конечные точки дороги.
* Строки N+1..N+M: Строка i+1 описывает шаг i. Первый символ этой строки либо P либо Q, которые описывают ФД садит траву или отвечает на вопрос. Затем следуют два разделенных пробелом целых числа Ai Bi (1 <= Ai, Bi <= N), которые описывают путь (для действия или вопроса)
Формат выходных данных
* Строки 1..???: Каждая строка содержит ответ на вопрос, в порядке поступления вопросов
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 6
1 4
2 4
3 4
P 2 3
P 1 3
Q 3 4
P 1 4
Q 2 4
Q 1 4
|
2
1
2
|