Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

El tío de Fito trabaja en la aerolínea Cubana de Aviación. Esta empresa presta servicios en varios países además del nuestro, y en cada uno de ellos está haciendo modificaciones en los vuelos con el fin de elevar la satisfacción de los clientes. En cada país hay una serie de vuelos entre algunos pares de ciudades, de forma tal que se puede ir de una ciudad a otra, posiblemente montando varios aviones, de una única forma. La empresa pretende cambiar uno de los vuelos de forma tal que la cantidad máxima de aviones que hay que tomar para ir de una ciudad a otra sea mínima. El cambio consiste en tomar un avión que viajaba entre cierto par de ciudades y ponerlo a viajar entre otro par de forma tal que siga habiendo una sola forma de viajar entre todo par de ciudades.

El tío de Fito quiere ganarse puntos en la empresa para ver si algún día llega a ser el director y le suben el salario. Para esto necesita que lo ayudemos a determinar para cada país la mejor forma de hacer el cambio.

Input

Habrá un caso de prueba independiente para cada país. Cada caso de prueba tendrá un entero $n$ ($4 \le n \le 2500$) que representa la cantidad de ciudades en el país. Después habrá $n-1$ líneas con dos enteros $a$, $b$ ($1 \le a$, $b \le n$) que significan que hay un avión que viaja entre las ciudades $a$ y $b$.

Output

La salida debe contener tres líneas. La primera de estas debe contener un entero indicando la mayor cantidad de aviones que es necesario tomar para ir de una ciudad a otra, después de hacer el cambio. La segunda línea debe contener dos enteros $a$, $b$ que representan las ciudades originales entre las que viaja el avión que se cambiaría y la tercera dos anteros $c$, $d$ que representan las ciudades entre las que viajará el avión después del cambio.

Nota : Se puede cambiar un vuelo por el mismo, en caso de que esto sea óptimo.

Sample test(s)