{"problem":{"name":"Spread of Information","description":{"content":"Takahashi Kingdom has $N$ towns, called Town $1$ through $N$. There are $N-1$ roads in this kingdom. The $i$\\-th road connects Town $u_i$ and Town $v_i$ bidirectionally. For any two towns $a$ and $b$,","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc116_e"},"statements":[{"statement_type":"Markdown","content":"Takahashi Kingdom has $N$ towns, called Town $1$ through $N$. There are $N-1$ roads in this kingdom. The $i$\\-th road connects Town $u_i$ and Town $v_i$ bidirectionally. For any two towns $a$ and $b$, it is possible to get from Town $a$ to Town $b$ by traversing some roads.\nTakahashi, the king, wants to spread some information all over the kingdom. Since he is busy, he can directly transmit this information to at most $K$ towns.\nAssume that Takahashi finishes transmitting the information at time $0$. Then, for each $t = 1, 2, 3, \\cdots$, the following happens:\n\n*   For towns $a$ and $b$ directly connected by a road, if $a$ has already received the information at time $t - 0.5$ but $b$ has not, $b$ receives it at time $t$.\n\nTakahashi wants to choose the $K$ towns to transmit the information to minimize the time taken until every town receives it. Find the minimum time this takes.\n\n## Constraints\n\n*   All values in input are integers.\n*   $1 \\leq K < N \\leq 2 \\times 10^5$\n*   $1 \\leq u_i, v_i \\leq N$\n*   For any two towns $a$ and $b$, it is possible to get from Town $a$ to Town $b$ by traversing some roads.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $K$ \n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_{N-1}$ $v_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc116_e","tags":[],"sample_group":[["5 2\n1 2\n2 3\n3 4\n4 5","1\n\nIf Takahashi directly transmits the information to Town $2$ and $4$, Town $1, 2, 3, 4, 5$ receives it at time $1, 0, 1, 0, 1$, respectively. In this case, the information is spread all over the kingdom at time $1$. We can prove that this is the earliest possible time."],["5 1\n1 2\n1 3\n1 4\n5 4","2"],["20 3\n2 15\n6 5\n12 1\n7 9\n17 2\n15 5\n2 4\n17 16\n12 2\n8 17\n17 19\n18 11\n20 8\n20 3\n13 9\n11 10\n11 20\n14 8\n11 7","3"]],"created_at":"2026-03-03 11:01:14"}}