{"problem":{"name":"E. Dragons in sleeping","description":{"content":"— And do dragons do the same when they want to get married? — Princess asked. — Dragons live alone. They come in existence in people's minds. And they evanesce when people forget about them, — Dragon","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10070E"},"statements":[{"statement_type":"Markdown","content":"— And do dragons do the same when they want to get married? — Princess asked.\n\n— Dragons live alone. They come in existence in people's minds. And they evanesce when people forget about them, — Dragon answered. \n\nDragon told Princess that when someone imagines a new dragon, a new castle appears in the Castles Valley in which the dragon lives. If nobody thinks about the dragon for a long time, he falls asleep.\n\nSometimes it unusual rains in the Castles Valley. There is no clouds in the sky, the sun shines brightly, but great raindrops knock frequently on the roof of the castle where dragon sleeps. And after the rain is over, a lawn with wildflowers appears in the place where the castle was before. Moreover, rainwater brooks flow along the lanes leading from this castle. If a brook reaches a castle of a waking dragon, it stops there. However, if it reaches a castle of sleeping dragon, this castle becomes a lawn, too, and a brook flows farther.\n\nAlthough dragons are only dreams, they feel for sleeping ones. They learned to foresee such rains, but they don't know which castle this rain will spill on. At the same time dragons want the number of appeared lawns to be as minimum as possible. They have a time to wake up exactly one of sleeping dragons before the rain. Now they want to know, in which castle they should wake up a dragon. Your task is to find it.\n\nFor the sake of simplicity, the input contains castles with sleeping dragons only. Also it is guaranteed that a path (consisting of one or more lanes) between every two castles exists.\n\nThe first line contains integers n and m (1 ≤ n ≤ 105,  1 ≤ m ≤ 2·105) — the number of castles with sleeping dragons and the number of lanes between castles.\n\nEach of the next m lines contains two integer — numbers of castles connected by the lane.\n\nIt is guaranteed that no more than one lane between any two castles exist. Also no one lane connects a castle with itself.\n\nPrint the only integer — number of a castle in which dragon should be woken up.\n\nIf there is more then one answer, output any of them.\n\n## Input\n\nThe first line contains integers n and m (1 ≤ n ≤ 105,  1 ≤ m ≤ 2·105) — the number of castles with sleeping dragons and the number of lanes between castles.Each of the next m lines contains two integer — numbers of castles connected by the lane.It is guaranteed that no more than one lane between any two castles exist. Also no one lane connects a castle with itself.\n\n## Output\n\nPrint the only integer — number of a castle in which dragon should be woken up.If there is more then one answer, output any of them.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ G = (V, E) $ be an undirected connected graph, where:  \n- $ V $ is the set of $ n $ vertices (castles with sleeping dragons),  \n- $ E $ is the set of $ m $ edges (lanes between castles).  \n\n**Objective**  \nFind a vertex $ v^* \\in V $ such that, if the rain starts at an arbitrary vertex and propagates along edges (converting sleeping dragon castles to lawns and stopping at waking dragons), the **maximum number of lawns created** over all possible rain starting points is **minimized**.  \n\nEquivalently:  \nChoose $ v^* \\in V $ to minimize  \n$$\n\\max_{u \\in V} \\left| \\{ w \\in V \\setminus \\{v^*\\} \\mid \\text{the unique path from } u \\text{ to } v^* \\text{ passes through } w \\} \\right|\n$$  \nThat is, wake the dragon at the vertex $ v^* $ that minimizes the size of the largest connected component in $ G - v^* $.  \n\n**Solution Target**  \nFind a vertex $ v^* $ that is a **centroid** of the tree $ G $ (i.e., removing $ v^* $ leaves no connected component with more than $ \\lfloor n/2 \\rfloor $ vertices).","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10070E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}