Hay un árbol de \(N\) ciudades numeradas de \(1\) a \(N\) en orden creciente de riqueza, con aristas de igual largo. Desde una ciudad \(i\), el ladrón va a la ciudad más cercana (en cantidad de aristas) que sea más rica que \(i\) (número mayor); si hay varias a la misma distancia, elige la de menor número. Si no hay ninguna ciudad más rica, se queda en \(i\).

Para cada ciudad \(i\), determina a qué ciudad va el ladrón.

Entrada

La primera línea tiene un entero \(N\) \((1 \le N \le 10^5)\).

Cada una de las siguientes \(N - 1\) líneas tiene dos enteros \(U\) y \(V\) \((1 \le U, V \le N,\ U \ne V)\): una arista. El grafo es conexo.

Salida

Una línea con \(N\) enteros: el \(i\)-ésimo es la ciudad a la que va el ladrón desde \(i\).

Ejemplo 1

Entrada

6
1 6
2 5
4 5
3 5
5 6

Salida

6 5 5 5 6 6

Ejemplo 2

Entrada

5
5 1
1 3
3 2
2 4

Salida

3 3 4 5 5

Ejemplo 3

Entrada

1

Salida

1

Regional Latinoamericana 2023 del ICPC, problema J («Journey of the Robber»). Versión en español redactada para este juez; el enunciado oficial, en inglés, está aquí abajo.