{"raw_statement":[{"iden":"statement","content":"Noura has been recently working on developing Android Applications with coach Alaa Jrad. One of her tasks was to develop an application to help coach Alaa with teaching Geometry to his contestants, so she decided to use coach Fegla's geometry library, as it is one of the best in the region. But while using coach Fegla's geometry library, if you need the code of the function IsPointOnSegment, for example, you will also need to include the function collinear in the code. In a similar manner, the function collinear might yet require other functions to run.\n\nGiven the dependencies of each function, and the list of the functions Noura will use, help her find the names of all the functions she needs to include from the library to get her code to compile.\n\nThe first line of input contains an integer T (1 ≤ T ≤ 128), the number of test cases.\n\nThe first line of each test case contains two space - separated integers N (1 ≤ N ≤ 105), the number of functions in the library, and K (1 ≤ K ≤ N) the number of the functions Noura will use. Then N lines follow, each line will be in the following format:\n\nSi Ci Fi, 1 Fi, 2 ... Fi, Ci\n\nWhere Si represents the name of the ith function, Ci (0 ≤ Ci ≤ i) represents the number of functions the ith function depends on, then followed by a list of Ci distinct function names, each represents the name of a function the ith function depends on. It's guaranteed that all function names in the list appeared in the input before. A function can depend on itself (recursive function).\n\nThe last line of each test case contains K distinct function names, the list of the functions that Noura is going to use.\n\nFunction name doesn't exceed 15 letters and contains only lowercase and uppercase English letters.\n\nFor each test case, print the functions Noura needs to include, each on a single line, following the same order of appearing in the input file.\n\nWarning: large Input/Output data, be careful with certain languages.\n\n"},{"iden":"input","content":"The first line of input contains an integer T (1 ≤ T ≤ 128), the number of test cases.The first line of each test case contains two space - separated integers N (1 ≤ N ≤ 105), the number of functions in the library, and K (1 ≤ K ≤ N) the number of the functions Noura will use. Then N lines follow, each line will be in the following format:Si Ci Fi, 1 Fi, 2 ... Fi, CiWhere Si represents the name of the ith function, Ci (0 ≤ Ci ≤ i) represents the number of functions the ith function depends on, then followed by a list of Ci distinct function names, each represents the name of a function the ith function depends on. It's guaranteed that all function names in the list appeared in the input before. A function can depend on itself (recursive function).The last line of each test case contains K distinct function names, the list of the functions that Noura is going to use.Function name doesn't exceed 15 letters and contains only lowercase and uppercase English letters."},{"iden":"output","content":"For each test case, print the functions Noura needs to include, each on a single line, following the same order of appearing in the input file."},{"iden":"examples","content":"Input22 1cross 0polygonArea 1 crosspolygonArea6 2intersect 0circlePoint 0intLines 1 intersectcircleThree 1 intersectcircleTwo 0mec 3 circlePoint circleTwo mecintersect mecOutputcrosspolygonAreaintersectcirclePointcircleTwomec"},{"iden":"note","content":"Warning: large Input/Output data, be careful with certain languages."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ N \\in \\mathbb{Z} $ be the number of functions in the library.  \n- Let $ K \\in \\mathbb{Z} $ be the number of functions Noura will use.  \n- Let $ F = \\{f_1, f_2, \\dots, f_N\\} $ be the ordered list of function names as they appear in input.  \n- Let $ D: F \\to \\mathcal{P}(F) $ be the dependency function, where $ D(f_i) $ is the set of direct dependencies of $ f_i $.  \n- Let $ S \\subseteq F $ be the set of initially used functions (given in last line of test case).  \n\n**Constraints**  \n1. $ 1 \\le T \\le 128 $  \n2. $ 1 \\le N \\le 10^5 $, $ 1 \\le K \\le N $  \n3. For each $ f_i \\in F $: $ 0 \\le |D(f_i)| \\le i $, and all dependencies of $ f_i $ appear in $ \\{f_1, \\dots, f_{i-1}\\} $  \n4. Function names are unique, up to 15 ASCII letters (a–z, A–Z).  \n\n**Objective**  \nFor each test case, compute the minimal closure $ C \\subseteq F $ such that:  \n- $ S \\subseteq C $,  \n- $ \\forall f \\in C $, $ D(f) \\subseteq C $.  \n\nOutput all functions in $ C $ in the order they first appeared in the input.","simple_statement":"Noura needs to find all functions to include when using some functions from a library, where each function may depend on others. Given the dependencies, output all required functions in the order they appear in the input.","has_page_source":false}