{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eDreamGrid has just found two trees, both consisting of $n$ vertices, in his right pocket. Each edge in each tree has its own weight. The $i$-th edge in the first tree has a weight of $a_i$, while the $i$-th edge in the second tree has a pair of weight, denoted by $(b_i, c_i)$.\u003c/p\u003e\n\n\u003cp\u003eLet ${}^1\\!u$ be the $u$-th vertex in the first tree, and ${}^2\\!u$ be the $u$-th vertex in the second tree. Let $\\mathbb{E}_1({}^1\\!u, {}^1\\!v)$ be the set containing the \u003cb\u003eindices\u003c/b\u003e of all the edges on the path between the $u$-th and the $v$-th vertex in the first tree. Similarly, let $\\mathbb{E}_2({}^2\\!u, {}^2\\!v)$ be the set containing the \u003cb\u003eindices\u003c/b\u003e of all the edges on the path between the $u$-th and the $v$-th vertex in the second tree. Define the following values:\n\n\u003c/p\u003e\u003cul\u003e\n \u003cli\u003e$A_{\\min}({}^1\\!u, {}^1\\!v) \u003d \\min\\{a_k | k \\in \\mathbb{E}_1({}^1\\!u, {}^1\\!v)\\}$\u003c/li\u003e\n \u003cli\u003e$B_{\\max}({}^2\\!u, {}^2\\!v) \u003d \\max\\{b_k | k \\in \\mathbb{E}_2({}^2\\!u, {}^2\\!v)\\}$\u003c/li\u003e\n \u003cli\u003e$C_{\\max}({}^2\\!u, {}^2\\!v) \u003d \\max\\{c_k | k \\in \\mathbb{E}_2({}^2\\!u, {}^2\\!v)\\}$\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e\u003c/p\u003e\n\n\u003cp\u003eAs DreamGrid is bored, he decides to count the number of good indices. DreamGrid considers an index $i$ ($1 \\le i \\le n$) is good, if for all $1 \\le j \\le n$ and $j \\ne i$, $A_{\\min}({}^1\\!i, {}^1\\!j) \\ge \\min(B_{\\max}({}^2\\!i, {}^2\\!j), C_{\\max}({}^2\\!i, {}^2\\!j))$. Please help DreamGrid figure out all the valid indices.\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003eThere are multiple test cases. The first line contains an integer $T$, indicating the number of test cases. For each test case:\u003c/p\u003e\n\n\u003cp\u003eThe first line contains an integer $n$ ($2 \\le n \\le 10^5$), indicating the number of vertices in both trees.\u003c/p\u003e\n\n\u003cp\u003eFor the following $(n-1)$ lines, the $i$-th line contains three integers ${}^1\\!u_i$, ${}^1\\!v_i$ and $a_i$ ($1 \\le {}^1\\!u_i, {}^1\\!v_i \\le n$, $1 \\le a_i \\le 10^9$), indicating that there is an edge, whose weight is $a_i$, connecting vertex $u_i$ and $v_i$ in the first tree.\u003c/p\u003e\n\n\u003cp\u003eFor the following $(n-1)$ lines,the $i$-th line contains four integers ${}^2\\!u_i$, ${}^2\\!v_i$, $b_i$ and $c_i$ ($1 \\le {}^2\\!u_i, {}^2\\!v_i \\le n$, $1 \\le b^2_i, c^2_i \\le 10^9$), indicating that there is an edge, whose weight is $(b_i, c_i)$, connecting vertex $u_i$ and $v_i$ in the second tree.\u003c/p\u003e\n\n\u003cp\u003eIt\u0027s guaranteed that the sum of $n$ of all test cases does not exceed $1.5 \\times 10^5$.\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003eFor each test case output $k$ integers ($k$ is the number of valid indices) in one line separated by a space in increasing order, indicating the indices of the valid vertices.\u003c/p\u003e\n\n\u003cp\u003eNote that if there is no valid vertex, you should print \"-1\" instead.\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\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\u003e2\n2\n1 2 1\n1 2 2 3\n4\n1 2 7\n1 3 8\n1 4 12\n1 2 8 8\n2 3 9 7\n2 4 6 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\n3 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n"}}]}