Escondidas.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 32M

Author:
Problem type
Allowed languages
C, C#, C++, Java, JS, Pascal, Python, VB

Bessie está jugando escondidas (un juego en el cual un número de jugadores se esconde y un solo jugador (el buscador) intenta encontrarlos después de lo cual se dan varios puntos y penalidades; se asegura usualmente mucha diversión).

Ella está tratando de encontrar en cual de los N (2 \leq N \leq 20,000) establos numerados convenientemente 1..N ella se debería esconder. Ella sabe que GJ (el buscador) comienza en el establo 1. Todos los establos están conectados por M (1 \leq M \leq 50,000) caminos bidireccionales con puntos extremos A_i y B_i (1 \leq A_i \leq N; 1 \leq B_i \leq N; A_i \neq B_i) es posible llegar a cualquier establo desde cualquier otro a través de los caminos.

Bessie decide que será lo más seguro esconderse en el establo que esté a la distancia más grande desde el establo 1 (la distancia entre dos establos es el menor número de caminos que uno debe recorrer para ir de uno al otro). Ayude a Bessie a encontrar el mejor establo en el cual esconderse.

Entrada

  • Línea 1: Dos enteros separados por espacio: N y M.
  • Líneas 2..M+1: La línea i+1 contiene los puntos extremos para el camino i: A_i y B_i

Ejemplo de Entrada

 6 7
 3 6
 4 3
 3 2
 1 3
 1 2
 2 4
 5 2

Detalles de la Entrada

La distribución de la granja es como sigue:

               1--2--5
               | /|
               |/ |
               3--4
               |
               6

Salida

  • Línea 1. En una sola línea, imprima tres enteros separados por espacios: el índice del establo más lejos del establo 1 (si hay varios de estos establos, imprima el menor de estos índices), el menor número de caminos necesarios para llegar a este establo desde el establo 1, y el número de establos con este número de caminos.

Ejemplo de Salida

4 2 3

Detalles de la Salida

Los establos 4, 5, y 6 están todos a distancia 2 del establo 1. Eligimos el establo 4 debido a que tiene el menor índice.


Comments

There are no comments at the moment.