D - Podobne miasta

W Bajtocji jest wiele miast. Każde miasto składa się z domów, sklepów i jednego ratusza. Każde miasto ma swój stopień. Stopień równy [asciimath]k[/asciimath] oznacza, że z każdego budynku (ratusz/dom/sklep) wychodzi dokładnie [asciimath]k[/asciimath] jednokierunkowych dróg (ponumerowanych od [asciimath]0[/asciimath] do [asciimath]k-1[/asciimath]). Dopuszczalne jest wiele dróg pomiędzy tymi samymi budynkami, jak i drogi które zaczynają się i kończą w tym samym budynku.

W tym zadaniu jesteśmy zainteresowani tylko takimi ścieżkami, które zaczynają się od ratusza. Każdą taką ścieżkę można opisać przez skończony ciąg liczb pomiędzy [asciimath]0[/asciimath] a [asciimath]k-1[/asciimath]. Przykładowo, ciąg liczb "1,0,3" oznacza:

  • Zacznij z ratusza. Następnie podążaj drogą o numerze 1 do budynku [asciimath]X[/asciimath].
  • Podążaj drogą o numerze 0 z budynku [asciimath]X[/asciimath] do budynku [asciimath]Y[/asciimath].
  • Podążaj drogą o numerze 3 z budynku [asciimath]Y[/asciimath] do budynku [asciimath]Z[/asciimath].
  • Ścieżka kończy się w budynku [asciimath]Z[/asciimath]. [asciimath]Z[/asciimath] może być ratuszem, domem lub sklepem.

Skończony ciąg liczb nazywamy właściwym jeżeli opisuje on ścieżkę z ratusza kończącą się w którymś z domów. Mówimy, że dwa miasta są do siebie podobne, jeżeli nie istnieje ciąg, który jest właściwy tylko w jednym mieście.

Mając dany opis dwóch miast o takim samym stopniu, twoim zadaniem jest napisać program, który sprawdzi czy są one do siebie podobne. Jeżeli nie są, to twój program powinien znaleźć najkrótszy ciąg liczb, który jest właściwy w jednym mieście, a nie jest właściwy w drugim mieście.

Wejście

W pierwszej linii znajduje się liczba zestawów testowych [asciimath]t (1 <= t <= 100)[/asciimath]. W kolejnych liniach znajdują się opisy poszczególnych zestawów testowych.

W pierwszej linii zestawu testowego znajduje się liczba [asciimath]k (1 <= k <= 10) [/asciimath]. Jest to stopień obu miast. W kolejnych liniach znajdują się dwa opisy miast.

W pierwszej linii opisu miasta znajdują się dwie liczby [asciimath]n (3 <= n <= 50) [/asciimath], [asciimath]d (1 <= d <= n - 2) [/asciimath]. Pierwsza liczba to liczba budynków w mieście. Druga liczba to liczba domów w mieście. Ratusz ma numer [asciimath]0[/asciimath], domy mają numery od [asciimath]1[/asciimath] do [asciimath]d[/asciimath], sklepy mają numery od [asciimath]d+1[/asciimath] do [asciimath]n-1[/asciimath].

W kolejnych [asciimath]n[/asciimath] liniach znajdują się opisy dróg. [asciimath]i[/asciimath]-ta linia to lista [asciimath]k[/asciimath] numerów budynków, do których prowadzą drogi zaczynające się w budynku o numerze [asciimath]i[/asciimath]. Lista dróg jest posortowana po numerach dróg, tj. pierwsza na liście jest droga o numerze [asciimath]0[/asciimath], a ostatnia o numerze [asciimath]k-1[/asciimath].

Wyjście

Dla każdego zestawu testowego należy wypisać:

  • PODOBNE MIASTA - jeżeli miasta są do siebie podobne
  • Jeżeli miasta nie są do siebie podobne, to należy wypisać dwie liczby [asciimath]a[/asciimath] [asciimath]b[/asciimath], gdzie:
    • [asciimath]a[/asciimath] to długość najkrótszego ciągu, który jest właściwy w pierwszym mieście, a nie jest właściwy w drugim mieście (lub [asciimath]-1[/asciimath] jeżeli nie ma takiego ciągu).
    • [asciimath]b[/asciimath] to długość najkrótszego ciągu, który jest właściwy w drugim mieście, a nie jest właściwy w pierwszym w mieście (lub [asciimath]-1[/asciimath] jeżeli nie ma takiego ciągu).

Przykład

Wejście:
2
1
3 1
1
2
0
3 1
1
2
2
2
4 1
2 0
1 3
2 1
3 3
6 2
4 3
2 5
2 5
4 3
4 1
5 5

Wyjście:
4 -1
PODOBNE MIASTA

Objaśnienie przykładu:

W pierwszym zestawie testowym miasta mają stopień 1.

Pierwsze miasto: 0 - ratusz; 1 - dom; 2 - sklep.
Drogi o numerach 0: 0->1, 1->2, 2->0
Właściwe ciągi to "0", "0,0,0,0", "0,0,0,0,0,0,0", "0,0,0,0,0,0,0,0,0,0", ...

Drugie miasto: 0 - ratusz; 1 - dom; 2 - sklep.
Drogi o numerach 0: 0->1, 1->2, 2->2
Jedynym właściwym ciągiem jest "0". Wszystkie inne ciągi zer opisują drogi kończące się w sklepie.

Te miasta nie są do siebie podobne. Najkrótszym ciągiem właściwym w pierwszym mieście, który nie jest właściwy w drugim mieście, to ciąg "0,0,0,0" (długość [asciimath]4[/asciimath]). Jedyny właściwy ciąg w drugim mieście jest także właściwy w pierwszym, dlatego drugą liczbą na wyjściu jest [asciimath]-1[/asciimath].

W drugim zestawie testowym miasta mają stopień 2.

Pierwsze miasto: 0 - ratusz; 1 - dom; 2, 3 - sklepy.
Drogi o numerach 0: 0->2, 1->1, 2->2, 3->3
Drogi o numerach 1: 0->0, 1->3, 2->1, 3->3

Drugie miasto: 0 - ratusz; 1, 2 - domy; 3, 4, 5 - sklepy.
Drogi o numerach 0: 0->4, 1->2, 2->2, 3->4, 4->4, 5->5
Drogi o numerach 1: 0->3, 1->5, 2->5, 3->3, 4->1, 5->5

Miasta są do siebie podobne. Każdy ciąg (zero lub więcej powtórzeń 1)(jeden lub więcej powtórzeń 0)1(zero lub więcej powtórzeń 0) jest właściwy w obu miastach.

Please log in to submit your solution.