Hola competidor, yo quiero jugar a algo contigo. Tu profesor esta en el salon donde se te tomara un examen con una BOMBA en sus manos. Esta bomba detonará en T segundos, y si esta denota en el salon donde estas dando examen tu moriras.

Yo puedo contarte algo sobre el edificio donde estas dando examen, este tiene N cuartos en total. Y para cada cuarto hay exactamente un tunel hacia otro cuarto, el cual solo puede ser usado en una direccion. Por ejemplo si el cuarto A se conecta con el cuarto B, luego tu puedes caminar de A a B, pero no puedes caminar de B hacia A, a no ser que claro haya un tunel de B hacia A.

La bomba tiene un mecanismo especial que detecta si tu profesor deja de moverse y si esto pasa la bomba explota matandote. Por esa razon tu profesor esta constantemente caminando entre los cuartos y le toma exactamente un segundo moverse entre cada tunel. La unica forma de salvar tu vida es que tu coach no este en tu cuarto cuando explote la bomba.

Tu no sabes nada acerca del edificio y su estructura, y puedes asegurar que los tuneles estan hechos de forma aleatoria y que ademas tu profesor escoge de forma aleatoria a que cuarto ir. Sin embargo se te da la posibilidad de escoger T, que es el tiempo en el que explotara la bomba, ese tiempo debe estar entre 2 y N inclusive. Tu tarea es determinar T de tal manera que este maximice tus probablilidades de sobrevivir.

Que comience el juego y que las probabilidades siempre esten de tu lado.

La entrada consiste de un entero N, representando cuantos cuartos existen en el edificio. N no sera mayor a 1 millon, se deben leer datos hasta que N sea 0.

La salida para cada caso de prueba es un entero T que maximiza tus probabilidades de sobrevivir.

Piensa en lo que ya sabes