{"code":"sgame4","name":"SGAME4","description":"Nông dân V.H.A có $N$ khu vườn để chăn nuôi chú gà [user:SPyofgame]. Các khu vườn được kết nối với nhau bằng $N-1$ con đường hai chiều, tức là chỉ có đúng một đường đi giữa hai khu vườn (giàu mà keo đây mà). Vì là một con gà béo tham lam nên [user:SPyofgame] đã đòi hỏi trên đường các con đường luôn phải có đồ ăn cho nó. Vì thế, V.H.A đã phải thực hiện các công việc sau:\r\n\r\n1. `P x y`: V.H.A sẽ chọn ra hai khu vườn và bỏ 1 nồi thóc dọc theo con đường nối hai khu vườn.\r\n2. `Q x y`: V.H.A sẽ phải trả lời trên đoạn đường nối hai khu vườn có bao nhiêu nồi thóc.\r\n\r\n#### Input:\r\n\r\n+ Dòng đầu tiên chứa hai số nguyên $N, M (1 \\leq M \\leq 100000, 2 \\leq N \\leq 100000).$\r\n+ $N-1$ dòng tiếp theo, mỗi dòng là hai số nguyên thể hiện hai đầu nối của một con đường.\r\n+ $M$ dòng cuối cùng, mỗi dòng là một truy vấn theo cấu trúc `P x y` hoặc `Q x y` $(1 \\leq x,y \\leq N)$.\r\n\r\n#### Output: \r\n+ Mỗi dòng là câu trả lời cho mỗi truy vấn `Q` theo thứ tự.\r\n####Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3 3\r\n        1 2\r\n        2 3\r\n        P 1 3\r\n        Q 2 3\r\n        Q 1 3\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        1\r\n        2\r\n        ```","points":500.0,"partial":true,"time_limit":2.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}