{"problem":{"name":"J. Smooth Developer","description":{"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","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":8000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10108J"},"statements":[{"statement_type":"Markdown","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## Input\n\nThe 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.\n\n## Output\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\n[samples]\n\n## Note\n\nWarning: large Input/Output data, be careful with certain languages.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10108J","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}