{"problem":{"name":"D. Recover a functional graph","description":{"content":"Functional graph is a directed graph in which all vertices have outdegree equal to 1. Loops are allowed. Some vertices of a functional graph lay on a cycle. From the others we can come to a cycle by ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF739D"},"statements":[{"statement_type":"Markdown","content":"Functional graph is a directed graph in which all vertices have outdegree equal to 1. Loops are allowed.\n\nSome vertices of a functional graph lay on a cycle. From the others we can come to a cycle by making a finite number of steps along the edges (we consider only finite functional graphs in this problem).\n\nLet's compute two values for each vertex. _precycle__i_ is the amount of edges we should pass to get to a vertex which is a part of some cycle (zero, if _i_ itself lies on a cycle), _cycle__i_ is the length of the cycle we get to.\n\nYou are given the information about these values for some functional graph. For each vertex you know the values _precycle__i_ and _cycle__i_, however, instead of some values there can be the question mark. It means that these values are unknown.\n\nBuild any functional graph that suits the description or determine that there is no such graph.\n\n## Input\n\nThe first line contains single integer _n_ (1 ≤ _n_ ≤ 300) — the number of vertices in the graph.\n\nEach of the next _n_ lines contain two integers — _precycle__i_ (0 ≤ _precycle__i_ ≤ _n_ - 1) and _cycle__i_ (1 ≤ _cycle__i_ ≤ _n_). There could be question marks instead of some of these values.\n\n## Output\n\nIn case there is no solution, print _\\-1_.\n\nOtherwise, print _n_ integers. _i_\\-th of them is the number of vertex to which the edge form the _i_\\-th vertex go.\n\nThe vertices should be in the same order as they go in input data.\n\nIf there are multiple solutions, print any of them.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"函数图是一个有向图，其中所有顶点的出度均为 $1$。允许自环。\n\n函数图中的某些顶点位于环上。其余顶点可以通过沿着边进行有限步移动到达某个环（本题中仅考虑有限函数图）。\n\n对于每个顶点，我们计算两个值：$\\text{precycle}_i$ 表示从顶点 $i$ 出发到达某个环上顶点所需经过的边数（若 $i$ 本身就在环上，则为零）；$\\text{cycle}_i$ 表示到达的环的长度。\n\n你已知某个函数图的这些值信息。对于每个顶点，你已知 $\\text{precycle}_i$ 和 $\\text{cycle}_i$，但其中某些值可能是问号，表示未知。\n\n请构造一个满足描述的函数图，或判定不存在这样的图。\n\n第一行包含一个整数 $n$（$1 ≤ n ≤ 300$）——图中顶点的数量。\n\n接下来的 $n$ 行，每行包含两个整数——$\\text{precycle}_i$（$0 ≤ \\text{precycle}_i ≤ n - 1$）和 $\\text{cycle}_i$（$1 ≤ \\text{cycle}_i ≤ n$）。其中某些值可能是问号。\n\n若无解，请输出 _-1_。\n\n否则，请输出 $n$ 个整数。第 $i$ 个整数表示从第 $i$ 个顶点出发的边指向的顶点编号。\n\n顶点的输出顺序应与输入顺序一致。\n\n若存在多个解，输出任意一个即可。\n\n## Input\n\n第一行包含一个整数 $n$（$1 ≤ n ≤ 300$）——图中顶点的数量。接下来的 $n$ 行，每行包含两个整数——$\\text{precycle}_i$（$0 ≤ \\text{precycle}_i ≤ n - 1$）和 $\\text{cycle}_i$（$1 ≤ \\text{cycle}_i ≤ n$）。其中某些值可能是问号。\n\n## Output\n\n若无解，请输出 _-1_。否则，请输出 $n$ 个整数。第 $i$ 个整数表示从第 $i$ 个顶点出发的边指向的顶点编号。顶点的输出顺序应与输入顺序一致。若存在多个解，输出任意一个即可。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ n \\leq 300 $, be the number of vertices.  \nFor each vertex $ i \\in \\{1, \\dots, n\\} $, let $ p_i \\in \\{0, 1, \\dots, n-1\\} \\cup \\{?\\} $ and $ c_i \\in \\{1, 2, \\dots, n\\} \\cup \\{?\\} $ denote the possibly unknown *precycle* and *cycle* values.\n\n**Constraints**  \n1. For each vertex $ i $:  \n   - If $ p_i \\neq ? $, then $ 0 \\leq p_i \\leq n-1 $.  \n   - If $ c_i \\neq ? $, then $ 1 \\leq c_i \\leq n $.  \n2. In any valid functional graph:  \n   - Each vertex has outdegree exactly 1.  \n   - For each vertex $ i $:  \n     - If $ p_i \\neq ? $, then the distance from $ i $ to the cycle it reaches is exactly $ p_i $.  \n     - If $ c_i \\neq ? $, then the cycle that $ i $ eventually reaches has length exactly $ c_i $.  \n   - All vertices that reach the same cycle must have the same $ c_i $.  \n   - For any two vertices $ i, j $:  \n     - If $ p_i = 0 $, then $ i $ lies on a cycle, and $ c_i $ must equal the length of that cycle.  \n     - If $ p_i > 0 $, then the vertex $ j $ to which $ i $ points must satisfy $ p_j = p_i - 1 $ and $ c_j = c_i $.  \n   - Vertices with $ p_i = 0 $ must form disjoint cycles, each of length $ c_i $, and no two such vertices in the same cycle may have different $ c_i $.\n\n**Objective**  \nConstruct a function $ f: \\{1, \\dots, n\\} \\to \\{1, \\dots, n\\} $ (representing the edge from each vertex) such that:  \n- $ \\forall i, \\; \\text{dist}(i, \\text{cycle}) = p_i $ (if $ p_i \\neq ? $),  \n- $ \\forall i, \\; \\text{cycle length containing } i = c_i $ (if $ c_i \\neq ? $),  \nor determine that no such $ f $ exists.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF739D","tags":["graph matchings"],"sample_group":[["3\n0 3\n0 3\n? ?","2 3 1"],["5\n3 2\n? ?\n? ?\n? ?\n? ?","5 3 2 2 4"],["8\n? 3\n? ?\n0 2\n0 2\n0 3\n0 3\n0 3\n3 3","5 1 4 3 6 7 5 2"],["1\n? ?","1"],["6\n0 3\n0 3\n0 3\n0 3\n0 3\n0 3","2 3 1 5 6 4"],["2\n1 1\n1 1","\\-1"]],"created_at":"2026-03-03 11:00:39"}}