Tala de Árboles
Después de que el Granjero Juan (GJ) se dio cuenta de que Bessie había instalado una red en "forma de árbol" entre sus graneros a un costo increíble, demandó a Bessie para mitigar sus pérdidas.
Bessie, sintiéndose vengativa, decidió sabotear la red del Granjero Juan cortando la energía a uno de los graneros (interrumpiendo así todas las conexiones que involucran ese granero). Cuando Bessie hace esto, se rompe la red en trozos más pequeños, cada uno de los cuales retiene conectividad dentro de sí mismo. Para ser lo más disruptivo posible, Bessie quiere asegurarse de que cada una de esas partes se conecte entre sí con no más de la mitad de los graneros de GJ.
Ayude a Bessie a determinar todos los establos que serían adecuados para desconectar.
Entrada
Línea 1: Un solo entero, . Los graneros están numerados .
Líneas 2…N: Cada línea contiene dos números enteros e , que representa una conexión entre los establos e .
Ejemplo de Entrada
10
1 2
2 3
3 4
4 5
6 7
7 8
8 9
9 10
3 8
Detalles de la Entrada
El conjunto de conexiones en la entrada describe un "árbol": conecta todos los graneros juntos y no contiene ciclos.
Salida
- Líneas 1…?: Cada línea contiene un solo entero, el número (de ) de un establo cuya remoción parte a la red en pedazos, donde cada uno tiene como máximo la mitad del número original de graneros. Los graneros deben mostrarse en la salida en orden numérico creciente. Si no hay graneros adecuados, la salida debe ser una sola línea que contenga la palabra "NONE".
Ejemplo de Salida
3
8
Detalles de la Salida
Si se elimina el granero o el granero , la red restante tendrá una pieza compuesta por graneros y dos piezas conteniendo graneros. Si se retira algún otro establo, entonces al menos una de las piezas restantes tiene un tamaño de al menos (que es más de la mitad del número original de graneros, ).
Comments