{"problem":{"name":"B. Brexit Negotiations","description":{"content":"As we all know, Brexit negotiations are on their way—but we still do not know whether they will actually finish in time. The negotiations will take place topic-by-topic. To organise the negotiations ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10248B"},"statements":[{"statement_type":"Markdown","content":"As we all know, Brexit negotiations are on their way—but we still do not know whether they will actually finish in time.\n\nThe negotiations will take place topic-by-topic. To organise the negotiations in the most effective way, the topics will all be discussed and finalised in separate meetings, one meeting at a time.\n\nThis system exists partly because there are (non-cyclic) dependencies between some topics: for example, one cannot have a meaningful talk about tariffs before deciding upon the customs union. The EU can decide on any order in which to negotiate the topics, as long as the mentioned dependencies are respected and all topics are covered.\n\nEach of the topics will be discussed at length using every available piece of data, including key results from past meetings. At the start of each meeting, the delegates will take one extra minute for each of the meetings that has already happened by that point, even unrelated ones, to recap the discussions and understand how their conclusions were reached. See the figure for an example.\n\nNobody likes long meetings. The EU would like you to help order the meetings in a way such that the longest meeting takes as little time as possible.\n\nThe input consists of:\n\n The $i$th such line starts with two integers $e_i$ and $d_i$ ($1 <= e_i <= 10^6$, $0 <= d_i < n$), the number of minutes needed to reach a conclusion on topic $i$ and the number of other specific topics that must be dealt with before topic $i$ can be discussed.\n\n The remainder of the line has $d_i$ distinct integers $b_{i , 1}, \\\\dots, b_{i , d_(i})$ ($1 <= b_{i , j} <= n$ and $b_{i , j} != i$ for each $j$), the list of topics that need to be completed before topic $i$. \n\nOutput the minimum possible length of the longest of all meetings, if meetings are arranged optimally according to the above rules.\n\n## Input\n\nThe input consists of:  One line containing an integer $n$ ($1 <= n <= 4 dot.op 10^5$), the number of topics to be discussed. The topics are numbered from $1$ to $n$. $n$ lines, describing the negotiation topics. The $i$th such line starts with two integers $e_i$ and $d_i$ ($1 <= e_i <= 10^6$, $0 <= d_i < n$), the number of minutes needed to reach a conclusion on topic $i$ and the number of other specific topics that must be dealt with before topic $i$ can be discussed. The remainder of the line has $d_i$ distinct integers $b_{i , 1}, \\\\dots, b_{i , d_(i})$ ($1 <= b_{i , j} <= n$ and $b_{i , j} != i$ for each $j$), the list of topics that need to be completed before topic $i$.  It is guaranteed that there are no cycles in the topic dependencies, and that the sum of $d_i$ over all topics is at most $4 dot.op 10^5$.\n\n## Output\n\nOutput the minimum possible length of the longest of all meetings, if meetings are arranged optimally according to the above rules.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T $ be a string over the alphabet $ \\Sigma = \\{ \\text{a-z}, \\text{,}, \\text{.}, \\text{ } \\} $.  \nLet $ W = (w_1, w_2, \\dots, w_m) $ be the sequence of words in $ T $, where each $ w_i $ is a maximal substring of consecutive lowercase letters.  \nLet $ P = (p_1, p_2, \\dots, p_m) $ be the positions of words in $ T $, where $ p_i $ is the index of the first character of $ w_i $.  \nLet $ L = (l_1, l_2, \\dots, l_m) $ be the list of left delimiters (characters immediately preceding each word) and $ R = (r_1, r_2, \\dots, r_m) $ be the list of right delimiters (characters immediately following each word), with $ l_i, r_i \\in \\{ \\text{space}, \\text{comma}, \\text{period}, \\text{none} \\} $.  \nLet $ C \\subseteq \\{1, \\dots, m\\} $ be the set of indices of words that have a comma as their right delimiter.  \nLet $ D \\subseteq \\{1, \\dots, m\\} $ be the set of indices of words that have a comma as their left delimiter.  \n\n**Constraints**  \n1. Words are separated by spaces, periods, or commas.  \n2. A word at the start of a sentence (immediately after a period or at the beginning of text) has no left delimiter.  \n3. A word at the end of a sentence (immediately before a period) has no right delimiter.  \n4. Commas may appear only between words, not at the start or end of text.  \n\n**Objective**  \nApply the following iterative rule until no more changes occur:  \n- For every word $ w_i $, if $ \\exists j \\ne i $ such that $ w_i = w_j $ and $ j \\in C $, then add $ i $ to $ C $ (i.e., insert a comma after $ w_i $ if the same word elsewhere has a comma after it).  \n- For every word $ w_i $, if $ \\exists j \\ne i $ such that $ w_i = w_j $ and $ j \\in D $, then add $ i $ to $ D $ (i.e., insert a comma before $ w_i $ if the same word elsewhere has a comma before it).  \n- Do **not** add commas before the first word of a sentence or after the last word of a sentence.  \n\nOutput the modified string $ T' $ with all required commas inserted according to $ C $ and $ D $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10248B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}