Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

LCITY - Oświetlone miasto

Wraz z końcem epoki Średniowiecza i nastaniem Światłych Nowych Czasów, w stolicy Bajtlandii otwarto pierwsze sklepy czynne całodobowo. Mieszkańcy radośnie przyjęli tę nowość. Do czasu. Wkrótce zaobserwowano nieoczekiwany wzrost drobnej przestępczości i liczby ulicznych bójek. Burmistrz postanowił przeznaczyć część budżetu miasta na oświetlenie sieci ulic miasta, przy czym z oczywistych względów chciałby to uczynić jak najmniejszym kosztem.

Sieć dwukierunkowych ulic miasta i skrzyżowań między nimi ma następujące własności:

  • Każde dwa skrzyżowania łączy co najwyżej jedna ulica.
  • Istnieje dokładnie jedna trasa przejazdu z dowolnie ustalonego skrzyżowania do dowolnego innego skrzyżowania.
  • Umieszczenie lampy ulicznej przy skrzyżowaniu oświetla wszystkie spotykające się w nim ulice, w związku z czym lampy postanowiono ustawiać tylko przy skrzyżowaniach.

 

System oświetlenia nazywamy optymalnym, jeżeli wszystkie ulice miasta są w nim oświetlone, a liczba użytych lamp jest najmniejsza możliwa.

Twoje zadanie polega na:

  • Wyznaczeniu liczby lamp ulicznych w optymalnym systemie oświetlenia.
  • Określeniu, spośród ilu optymalnych systemów oświetleń burmistrz może wybierać.

 

Wejście

W pierwszej linii wejścia podana jest liczba przypadków testowych t (t<=20). W pierwszej linii każdego przypadku testowego podana jest liczba całkowita n, określająca liczbę skrzyżowań w stolicy (1 <= n <= 100010). W kolejnych n-1 liniach podane są opisy poszczególnych ulic, w postaci pary liczb całkowitych a b, oznaczających skrzyżowania, które łączy dana ulica (1<= a,b <=n).

Wyjście

Dla każdego przypadku testowego należy wypisać linię zawierającą dwie liczby całkowite oddzielone spacją. Pierwsza z nich powinna oznaczać liczbę lamp ulicznych w optymalnym systemie oświetlenia, druga - resztę z dzielenia przez 10007 liczby różnych optymalnych systemów oświetlenia, które można zrealizować w stolicy.

Przykład

Wejście:
2 
4 
1 2 
2 3 
3 4 
3 
1 2 
1 3 

Wyjście:
2 3 
1 1

Dodane przez:adrian
Data dodania:2006-05-28
Limit czasu wykonania programu:1.976s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:Kashyap / FIPC

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.