{"problem":{"name":"B. Let me sleep","description":{"content":"Hasan is lazy. He likes to stay asleep in the morning. But the dorm's supervisor always wakes him up. He will try to run from her. The dorm consists of $N$ rooms. There are $M$ portals between these ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10216B"},"statements":[{"statement_type":"Markdown","content":"Hasan is lazy. He likes to stay asleep in the morning. But the dorm's supervisor always wakes him up. He will try to run from her.\n\nThe dorm consists of $N$ rooms. There are $M$ portals between these rooms. To catch Hasan, the supervisor will stand at one of these portals. The supervisor can catch Hasan only if she stands in a portal between two rooms such that this portal is the only way to get between these two rooms.\n\nHasan can add one portal between any two rooms in the dorm; if he added it optimally, what is the minimum number of portals that the supervisor can use to catch him.\n\nFirst line of the input will be $T$, the number of test cases.\n\nEach test case starts with a line of two numbers, $N$, $M$ ($1 <= N, M <= 10^5$)the number of rooms and portals.\n\nNext $M$ lines contain two integers, $u$ and $v$ the rooms of the $i_{t h}$ portal($1 <= u, v <= N$).\n\nFor each test case, print one line, the minimum number of portals that the supervisor can use to catch him.\n\n## Input\n\nFirst line of the input will be $T$, the number of test cases.Each test case starts with a line of two numbers, $N$, $M$ ($1 <= N, M <= 10^5$)the number of rooms and portals.Next $M$ lines contain two integers, $u$ and $v$ the rooms of the $i_{t h}$ portal($1 <= u, v <= N$).\n\n## Output\n\nFor each test case, print one line, the minimum number of portals that the supervisor can use to catch him.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ G = (V, E) $ be an undirected graph with $ |V| = N $ vertices (rooms) and $ |E| = M $ edges (portals).  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq \\text{number of test cases} $  \n2. For each test case: $ 1 \\leq N, M \\leq 10^5 $  \n3. Each edge connects two vertices $ u, v \\in V $, $ u \\neq v $  \n\n**Objective**  \nThe supervisor can catch Hasan only at **bridges** (edges whose removal increases the number of connected components).  \n\nHasan may add **exactly one** edge between any two vertices (possibly already connected).  \n\nFind the **minimum possible number of bridges** in $ G $ after adding one edge optimally.  \n\nThat is, compute:  \n$$\n\\min_{e' \\in \\binom{V}{2}} \\left( \\text{number of bridges in } G + \\{e'\\} \\right)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10216B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}