Kapitan Mambeks postanowił odwiedzić swoja rodzinę. W tym celu zebrał wszystkie swoje gwiezdne mapy, wczytał je do swojego programu, obliczył koszty i zaczął przygotowywać trasę podróży. Niestety otrzymał tajną informacje od swojego agenta, o panującym wirusie zakłócającym obliczenia programów bez jawnych błędów. Teraz przed kapitanem stoi bardzo trudne zadanie, zweryfikowanie poprawności wyliczonej trasy. W galaktyce Centra Handlowe
łączą się za pomocą hipertuneli. Kapitan uznał, że do weryfikacji wystarczy mu policzenie ilości Centr Handlowych na które będzie musiał natrafić podczas swej podróży. Twoim zadaniem jest stworzenie programu który pomoże Kapitanowi weryfikacje obliczeń.
Dane wejściowe:
W pierwszym wierszu zapisana jest liczba zestawów danych wejściowych. W kolejnych wierszach jest zapisanych n zestawów danych wejściowych. Każdy zestaw składa się z :
N – liczba połączeń między Centrami Handlowymi, 100000 >= N >= 2.
N linii zawierających pary stringów A B oznaczających połączenie ze sobą dwóch Centr
Handlowych.
X Y - stringi oznaczające początek i koniec podróży, stringi (o długości do 30 znaków).
Dane wyjściowe
Dla każdego zestawu danych wejściowych program ma wypisać w kolejnych
wierszach:
Z – liczba minimalnych Centr Handlowych na które natrafi kapitan podczas podróży.
Przykładowe dane wejściowe:
2
3
Malex Bukos
Bukos Rox
Rox Wex
Malex Wex
3
Malex Bukos
Bukos Rox
Rox Malex
Malex Rox
Przykładowe dane wyjściowe:
3
1