n - 1 and connected by roads: roads[i] = [u, v] is a road between villages u and v. There are exactly n - 1 roads, and every village can be reached from every other one.
A piece of news appears in one village at time 0. Every second, all villages next to a village that already knows it hear the news too.
For every village i, find which village hears the news last if it starts in i. Return an array whose i-th element is the answer for village i.
The input is such that for every starting village exactly one village is the last to hear.roads=[[0, 1], [1, 2], [2, 3]] → [3, 3, 0, 0]
The villages form a chain 0–1–2–3. Starting from 0 or 1 the news reaches 3 last; starting from 2 or 3 it reaches 0 last.
roads=[[0, 1]] → [1, 0]
Two villages: each one hears last when the news starts in the other.
roads=[[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [2, 6]] → [5, 5, 5, 0, 0, 0, 5]
The main road runs 0–1–2–3–4–5, with village 6 off to the side of village 2. From 6 it takes four roads to reach 5 but only three to reach 0, so 5 hears last. From 3, village 0 is three roads away, farther than 5 or 6.
roads=[[0, 1], [1, 2], [2, 3]]
[3, 3, 0, 0]
Run checks the first 3 tests in your browser. Submit checks all 16 tests on the server, hidden ones included.