Un árbol de \(n\) nodos (numerados de \(1\) a \(n\)) recibió una arista extra entre dos nodos distintos que no estaban unidos directamente, así que ahora tiene exactamente un ciclo. Se dan las \(n\) aristas. Encuentra una arista que se pueda quitar para que vuelva a ser un árbol; si hay varias, la que aparece última en la entrada.

Entrada

La primera línea tiene \(n\) \((3 \le n \le 10^5)\). Cada una de las siguientes \(n\) líneas tiene una arista \(a\) \(b\) \((a < b)\).

Salida

La arista, en el formato \(a\) \(b\).

Ejemplo 1

Entrada

3
1 2
1 3
2 3

Salida

2 3

Ejemplo 2

Entrada

5
1 2
2 3
3 4
1 4
1 5

Salida

1 4