P1670 [USACO04DEC] Tree Cutting S

John realized that Bessie’s network cost him a lot and fired her. Angry, Bessie plans to take revenge. She wants to damage John’s newly built network. John’s network is a tree connecting $N$ barns. She plans to cut power to one barn, causing all cables incident to that barn to be disconnected. Afterwards, the network will split into several subnetworks. To ensure the damage is large enough, in each subnetwork the number of barns must be no more than half of the total number of barns. Which barns are worth sabotaging?

Line $1$: an integer $N$. Lines $2$ to $N$: each line contains two integers, the endpoints of a cable.

Output, in increasing order, all barns that are worth sabotaging. If none are worth sabotaging, output `NONE`.

$1 \le N \le 10^4$. Translated by ChatGPT 5