F. Tree Restoration

Codeforces

IDCF10175F

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

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 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. If 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. ## Input The 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. ## Output If 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. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the number of vertices, with $ 1 \leq n \leq 1000 $. For 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 $. **Constraints** 1. $ 0 \leq c_i \leq n $ for all $ i \in \{1, \dots, n\} $ 2. All elements in $ S_i $ are distinct and satisfy $ 1 \leq a_{ij} \leq n $ 3. The successor relation must be consistent with a **tree** structure: - There is exactly one root (vertex with no parent). - Every other vertex has exactly one parent. - The successor relation is transitive and acyclic. - If $ j \in S_i $, then $ S_j \subset S_i $ (transitivity of successors). - $ i \notin S_i $ (no self-loops). - The union of all $ S_i $ must cover all non-root vertices exactly once as direct children in some valid parent-child assignment. **Objective** Determine 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 $. - If such a tree exists, output "YES" followed by $ n-1 $ parent-child edges $ (u, v) \in E $. - Otherwise, output "NO".

API Response (JSON)

{
  "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 contain...",
      "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\\} $ de...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments