{"trustable":true,"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":"\u003cdiv class\u003d\"panel_content\"\u003eLittle Q and Little T are playing a game on a tree. There are $n$ vertices on the tree, labeled by $1,2,...,n$, connected by $n-1$ bidirectional edges. The $i$-th vertex has the value of $w_i$.\u003cbr\u003eIn this game, Little Q needs to grab some vertices on the tree. He can select any number of vertices to grab, but he is not allowed to grab both vertices that are adjacent on the tree. That is, if there is an edge between $x$ and $y$, he can\u0027t grab both $x$ and $y$. After Q\u0027s move, Little T will grab all of the rest vertices. So when the game finishes, every vertex will be occupied by either Q or T.\u003cbr\u003eThe final score of each player is the bitwise XOR sum of his choosen vertices\u0027 value. The one who has the higher score will win the game. It is also possible for the game to end in a draw. Assume they all will play optimally, please write a program to predict the result.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input contains an integer $T(1\\leq T\\leq20)$, denoting the number of test cases.\u003cbr\u003eIn each test case, there is one integer $n(1\\leq n\\leq 100000)$ in the first line, denoting the number of vertices.\u003cbr\u003eIn the next line, there are $n$ integers $w_1,w_2,...,w_n(1\\leq w_i\\leq 10^9)$, denoting the value of each vertex.\u003cbr\u003eFor the next $n-1$ lines, each line contains two integers $u$ and $v$, denoting a bidirectional edge between vertex $u$ and $v$.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, print a single line containing a word, denoting the result. If Q wins, please print Q. If T wins, please print T. And if the game ends in a draw, please print D.\u003cbr\u003e"}},{"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\r\n3\r\n2 2 2\r\n1 2\r\n1 3\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eQ\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}