Berek

23.11.2011

Berek

Limit czasowy: 5000 milisekund
Limit pamięciowy: 128000 kilobajtów


Jedną z ulubionych zabaw podwórkowych Kornelii jest berek, w którego zwykle bawi się ze swoją koleżanką Joasią. Podwórko na którym odbywa się zabawa składa się z N zakątków (ponumerowanych od 1 do N) połączonych N-1 przejściami i wiemy, że z każdego zakątka podwórka da się dostać do każdego innego.

W momencie rozpoczęcia zabawy Kornelia znajduje się w zakątku K, Joasia w zakątku J i zadaniem Kornelii jest złapanie Joasi. Dziewczynki biegną z taką samą prędkością, i pokonanie jednego przejścia zajmuje każdej z nich dokładnie jedną chwilę. Na początku każdej chwili każda z dziewczynek wybiera, do którego z sąsiednich (tj. połączonych z obecnym) zakątków chce pobiec. Na końcu danej chwili dziewczynki są już w nowych zakątkach podwórka i cały proces zaczyna się od początku, aż do momentu w którym obie dziewczynki znajdą się w tym samym zakątku, tj. do momentu kiedy Kornelia złapie Joasię.

Dziewczynki wybierają zakątek do którego chcą pobiec według następujących reguł:

  • Kornelia zawsze wybiera ten spośród sąsiednich zakątków, który leży na ścieżce prowadzącej do zakątka, w którym aktualnie znajduje się Joasia (tj. biegnie w stronę Joasi).
  • Joasia biegnie tam, gdzie się jej podoba, ale nigdy nie wybiera przejścia do zakątka, w którym aktualnie znajduje się Kornelia. Joasia może zdecydować, że w danej chwili nigdzie nie biegnie (tj. przez jedną chwilę zostaje w tym zakątku, w którym teraz jest).

Hektor obserwuje zabawę z okna swojego pokoju i zastanawia się, ile maksymalnie chwil zajmie Kornelii złapanie Joasi (tj. ile czasu potrwa zabawa jeśli Joasia będzie podejmowała optymalne, prowadzące do najdłuższego czasu pościgu, decyzje). Czy potrafisz napisać program który rozwiąże ten problem za Hektora?

Wejście

W pierwszej linii znajduje się liczba naturalna Z ( 1 <= Z <= 10 ) oznaczająca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.

W pierwszej linii opisu pojedynczego zestawu testowego znajdują się trzy oddzielone pojedynczymi spacjami liczby naturalne N, K i J (2 <= N <= 1000000 | 1 <= K, J <= N K różne od J). W kolejnych N-1 liniach zestawu opisywane będą kolejne przejścia między zakątkami podwórka.

Opis pojedynczego przejścia składa się z dwóch oddzielonych pojedynczą spacją liczb naturalnych ai i bi (1 <= ai , bi <= N), które oznaczają obecność dwukierunkowego przejścia pomiędzy zakątkami ai i bi.

Wyjście

Dla każdego zestawu testowego należy w osobnej linii wypisać maksymalny czas trwania zabawy (wyrażony w chwilach). Kolejność wypisywanych odpowiedzi musi odpowiadać kolejności zestawów na wejściu.

Przykład

Wejście Wyjście
2
2 1 2
1 2
5 4 3
1 2
2 3
3 4
3 5
1
3
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com