Задача: Grass Planting

У Фермера Джона есть 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, которые описывают ФД садит траву или отвечает на вопрос. Затем следуют два разделенных пробелом целых числа A_i B_i (1 <= A_i, B_i <= N), которые описывают путь (для действия или вопроса)
Формат выходных данных
* Строки 1..???: Каждая строка содержит ответ на вопрос, в порядке поступления вопросов

Ваш ответ: