{"raw_statement":[{"iden":"statement","content":"Having just completed a course in graph algorithms, Bessie the cow has begun\ncoding her very own graph visualizer! Currently, her graph visualizer is only\ncapable of visualizing rooted trees with nodes of distinct values, and it can\nonly perform one kind of operation: merging.\n\nIn particular, a merging operation takes any two distinct nodes in a tree with\nthe same parent and merges them into one node, with value equal to the maximum\nof the values of the two nodes merged, and children a union of all the children\nof the nodes merged (if any).\n\nUnfortunately, after Bessie performed some merging operations on a tree, her\nprogram crashed, losing the history of the merging operations she performed. All\nBessie remembers is the tree she started with and the tree she ended with after\nshe performed all her merging operations. \n\nGiven her initial and final trees, please determine a sequence of merging\noperations Bessie could have performed. It is guaranteed that a sequence exists.\n\nEach input consists of $T$ independent test cases. It is\nguaranteed that the sum of $N$  over all test cases does not exceed $1000$."},{"iden":"input","content":"The first line contains $T$, the number of independent test cases. Each test\ncase is formatted as follows.\n\nThe first line of each test case contains the number of nodes $N$ in Bessie's initial tree, which have values $1\\dots N$. \n\nEach of the next $N-1$ lines contains two space-separated node values $v_i$ and\n$p_i$ indicating that the node with value $v_i$ is a\nchild node of the node with value $p_i$ in Bessie's initial tree.\n\nThe next line contains the number of nodes $M$ in Bessie's\nfinal tree. \n\nEach of the next $M-1$ lines contains two space-separated node values $v_i$ and\n$p_i$ indicating that the node with value $v_i$ is a\nchild node of the node with value $p_i$ in Bessie's final tree."},{"iden":"output","content":"For each test case, output the number of merging operations, followed by an\nordered sequence of merging operations of that length, one per line. \n\nEach merging operation should be formatted as two distinct space-separated\nintegers: the values of the two nodes to merge in any order. \n\nIf there are multiple solutions, output any."},{"iden":"note","content":"$1\\le T\\le 100$, $2 \\leq N \\leq 1000$, $1 \\leq v_i, p_i \\leq N$,$2 \\leq M \\leq N$.\n\n- Inputs 2-6: The initial and final trees have the same number of leaves.\n- Inputs 7-16: No additional constraints."}],"translated_statement":null,"sample_group":[["1\n8\n7 5\n2 1\n4 2\n5 1\n3 2\n8 5\n6 2\n4\n8 5\n5 1\n6 5\n","4\n2 5\n4 8\n3 8\n7 8\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}