26818번 - Najdłuższe ścieżki 다국어

문제

Bajtazar na lekcji informatyki dowiedział się, co to jest graf. Wie już, że jest to zbiór N wierzchołków, które mogą być połączone krawędziami. Wie również, że graf spójny to taki, który jest „w jednym kawałku”, czyli między dowolnymi dwoma wierzchołkami istnieje jakieś połączenie (być może przechodzące przez inne wierzchołki). Cykl zaś to ciąg wierzchołków, po których możemy jeździć „w kółko”, formalnie: jest to taki ciąg v₁, v₂, · · · v_k, że istnieje krawędź pomiędzy każdymi dwoma kolejnymi wierzchołkami v_i i v_i+1 oraz pomiędzy pierwszym i ostatnim (v₁ i v_k).

Zgłębiając kolejne strony internetowe, Bajtazar zapragnął poeksperymentować trochę ze specjalnymi typami grafów, mianowicie z drzewami i meduzami.

Graf nazywamy drzewem, jeśli jest spójny oraz nie zawiera cykli. Meduza natomiast powstaje z dowolnego drzewa, do którego dodamy dokładnie jedną krawędź pomiędzy dowolnymi dwoma różnymi wierzchołkami, które nie są połączone krawędzią. Zauważ, że oznacza to, że meduza będzie zawsze zawierać dokładnie jeden cykl.

Poprzez najkrótszą ścieżkę pomiędzy dwoma wierzchołkami będziemy rozumieli najkrótszą możliwość przejścia pomiędzy tymi wierzchołkami (złożoną z kolejnych krawędzi). Formalnie, jest to taki ciąg wierzchołków v₁, v₂ · · · v_t, że są one parami różne oraz każde kolejne dwa v_i oraz v_i+1 są połączone krawędzią. Dla przykładu, poniżej zaznaczyliśmy na czerwono najkrótsze ścieżki pomiędzy wierzchołkami 1 i 6. Zauważ, że w meduzie najkrótsza ścieżka nie biegnie przez wierzchołek 4, jako że taka droga nie byłaby najkrótsza.

Bajtazar chciałby poznać długość najdłuższej spośród najkrótszych ścieżek w jego grafie oraz na ile sposobów może taką ścieżkę wybrać. Przy liczeniu liczby różnych ścieżek Bajtazar przyjmuje, że dwie ścieżki są różne, jeśli różnią się co najmniej jednym wierzchołkiem (niekoniecznie końcowym).

입력

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N (1 ≤ N ≤ 500 000) oraz M oddzielone pojedynczym odstępem określające odpowiednio liczbę wierzchołków oraz liczbę krawędzi grafu. Liczba M będzie zawsze równa albo N (dla meduzy) albo N − 1 (dla drzewa).

W kolejnych M wierszach znajduje się opis krawędzi grafu: i-ty z nich składa się z dwóch liczb naturalnych U_i oraz V_i (1 ≤ U_i, V_i ≤ N, U_i ≠ V_i) określających numery wierzchołków, które są połączone krawędzią. Możesz założyć, że żadna krawędź się nie powtarza.

출력

Twój program powinien wypisać na wyjście dokładnie dwa wiersze. W pierwszym z nich powinna się znaleźć długość najdłuższej ścieżki w grafie z wejścia. W drugim powinna się znaleźć liczba różnych takich ścieżek.

제한

힌트