{"problem":{"name":"F. Tree Restoration","description":{"content":"There is a tree of n vertices. For each vertex a list of all its successors is known (not only direct ones). It is required to restore the tree or to say there is no such tree. The first line contain","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10175F"},"statements":[{"statement_type":"Markdown","content":"There is a tree of n vertices. For each vertex a list of all its successors is known (not only direct ones). It is required to restore the tree or to say there is no such tree.\n\nThe first line contains a single integer n (1 ≤ n ≤ 1000) — the number of vertices in the tree.\n\nEach of the next n lines contains an integer ci (0 ≤ ci ≤ n) — the number of successors of vertex i, and then ci distinct integers aij (1 ≤ aij ≤ n) — the indices of successors of vertex i.\n\nIf the answer does not exist, output «_NO_».\n\nOtherwise, in the first line output «_YES_», and then output n - 1 lines containing two integers each — indices of parent and child. Pairs (parent, child) can be output in any order.\n\n## Input\n\nThe first line contains a single integer n (1 ≤ n ≤ 1000) — the number of vertices in the tree.Each of the next n lines contains an integer ci (0 ≤ ci ≤ n) — the number of successors of vertex i, and then ci distinct integers aij (1 ≤ aij ≤ n) — the indices of successors of vertex i.\n\n## Output\n\nIf the answer does not exist, output «_NO_».Otherwise, in the first line output «_YES_», and then output n - 1 lines containing two integers each — indices of parent and child. Pairs (parent, child) can be output in any order.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of vertices, with $ 1 \\leq n \\leq 1000 $.  \nFor each vertex $ i \\in \\{1, \\dots, n\\} $, let $ S_i \\subseteq \\{1, \\dots, n\\} \\setminus \\{i\\} $ denote the set of successors of $ i $, with $ |S_i| = c_i $.\n\n**Constraints**  \n1. $ 0 \\leq c_i \\leq n $ for all $ i \\in \\{1, \\dots, n\\} $  \n2. All elements in $ S_i $ are distinct and satisfy $ 1 \\leq a_{ij} \\leq n $  \n3. The successor relation must be consistent with a **tree** structure:  \n   - There is exactly one root (vertex with no parent).  \n   - Every other vertex has exactly one parent.  \n   - The successor relation is transitive and acyclic.  \n   - If $ j \\in S_i $, then $ S_j \\subset S_i $ (transitivity of successors).  \n   - $ i \\notin S_i $ (no self-loops).  \n   - The union of all $ S_i $ must cover all non-root vertices exactly once as direct children in some valid parent-child assignment.\n\n**Objective**  \nDetermine whether there exists a directed tree $ T = (V, E) $ with $ V = \\{1, \\dots, n\\} $ such that for each $ i $, the set of successors of $ i $ in $ T $ (including indirect) is exactly $ S_i $.  \n- If such a tree exists, output \"YES\" followed by $ n-1 $ parent-child edges $ (u, v) \\in E $.  \n- Otherwise, output \"NO\".","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10175F","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}