{"trustable":false,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003csection\u003e\n\u003cp\u003eThere is a company with n employees (numbered from 1 to n), where each employee has a direct supervisor (excluding the leader of the entire company). If you are someone\u0027s direct supervisor, then that person is your subordinate, and all of their subordinates are also your subordinates. If you don\u0027t have a supervisor, then you are the leader of the entire company. This means that these n employees form a tree structure.\u003c/p\u003e\n\n\u003cp\u003eCompanies typically assign tasks to some employees to complete. When a task is assigned to someone, they assign it to all of their subordinates. In other words, that person and all of their subordinates simultaneously receive the task. Additionally, whenever an employee receives a task, they stop their current task (if any) and start the new one.\u003c/p\u003e\n\nWrite a program to help determine the current tasks of certain employees after the company assigns tasks.\u003c/p\u003e\n\u003c/section\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003csection\u003e\n\u003cp\u003eThe first line contains a single positive integer $t$ $(1 \\leq t \\leq 10)$, indicates the number of test cases.\u003c/p\u003e\n\n\u003cp\u003eFor each test case:\u003c/p\u003e\n\n\u003cp\u003eThe first line contains an integer $n$ $(n \\leq 5 \\cdot 10^4)$ , which is the number of the employees.\u003c/p\u003e\n\n\u003cp\u003eThe following $n - 1$ lines each contain two integers $u$ and $v$, which means the employee $v$ is the immediate boss of employee $u$ $(1 \\leq u,v \\leq n)$.\u003c/p\u003e\n\n\u003cp\u003eThe next line contains an integer $m$ $(m \\leq 5 \\cdot 10^4)$. The following $m$ lines each contain a message with following two types:\u003c/p\u003e\n\n\u003cp\u003e\"$C$ $x$\" which means an inquiry for the current task of employee $x$. $(1 \\leq x \\leq n)$\u003c/p\u003e\n\u003cp\u003e\"$T$ $x$ $y$\"which means the company assign task $y$ to employee $x$. $(1 \\leq x \\leq n),(0 \\leq y \\leq 10^9)$\u003c/p\u003e\n\n\n\u003c/section\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, print the test case number (beginning with 1) in the first line and then for every inquiry, output the correspond answer per line."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 \n5 \n4 3 \n3 2 \n1 3 \n5 2 \n5 \nC 3 \nT 2 1\nC 3 \nT 3 2 \nC 3\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1:\n-1 \n1 \n2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}