{"trustable":false,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"Problem Statement","value":{"format":"MD","content":"The players have now exited the abyss, and it\u0027s time for the most difficult task in Genshin Impact - PvP.\n\nGenshin Impact is known to offer \"offline PvP\", where players can argue over how strong a character or weapon is. The war has gone so bad in Bilibili that you decided to remind the players about the human ancestor theory.\n\nIn some theory, humans on this planet may be traced back to the same ancestor. So your task in this problem is to find the lowest common ancestor of two nodes, $v$ and $w$, in a tree."}},{"title":"Concepts","value":{"format":"MD","content":"A tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree. - Wikipedia\n\nThe lowest common ancestor (LCA) is a concept in graph theory and computer science. Let T be a rooted tree with N nodes. The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself). - Wikipedia\n\n \u003ch3 style\u003d\"text-align: center;\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/7afea78784a923fb816b4d48a8b1dcab?v\u003d1688814635\" alt\u003d\"\"\u003e\u003c/h3\u003e\n \u003cp\u003e\u003cstrong\u003eFor example the LCA of nodes 9 and 12 in this tree is the node number 3.\u003c/strong\u003e\u003c/p\u003e"}},{"title":"Warning","value":{"format":"MD","content":"**NOTE:** C++ users, please note that C++ 17 and above cannot be used for this problem. Please write C++ syntax up to C++ 14.\n\n**NOTE:** The time limit for this problem is `600ms`. It is a lot tighter than other problems in this contest."}},{"title":"Input","value":{"format":"MD","content":"The first line of input is $t$ - the number of test cases ($1 \\le t \\le 500$).\n\nThe first line of each test case will contain a number $N$ - the number of nodes in the tree ($1 \\le N \\le 1000$). Nodes are numbered from 1 to N.\n\nEach of the next $N$ lines will start with a number $M$, representing the number of child nodes of the N-th node ($0 \\le M \\le 999$), followed by $M$ numbers, representing child nodes of the N-th node.\n\nThe next line is a number $Q$ - the number of queries ($1 \\le Q \\le 1000$).\n\nEach of the next $Q$ lines will have two numbers, $v$ and $w$ ($1 \\le v, w \\le 1000$). You will need to find the LCA of $v$ and $w$ in the tree.\n\nInput will guarantee that there is only one root and no cycles."}},{"title":"Output","value":{"format":"MD","content":"For each test case, output $Q + 1$ lines.\n\nThe first line must say **“Case C:”** without quotes where $C$ is the case number starting from 1.\n\nThe next $Q$ lines should be the LCA of the given nodes, $v$ and $w$, respectively."}},{"title":"Sample","value":{"format":"MD","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\n7\n3 2 3 4\n0\n3 5 6 7\n0\n0\n0\n0\n2\n5 7\n2 7\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1:\n3\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003csection\u003e\n\u003c/section\u003e\u003csection\u003e\n\u003c/section\u003e"}}]}