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.|

FR_14_16 - K2

Na K2 znajduje się n punktów ponumerowanych liczbami od 1 do n. Są to punkty, gdzie wspinacze mogą odpocząć. Pomiędzy tymi punktami poprowadzonych jest n - 1 lin poręczowych o różnej grubości. Korzystając z tych lin wspinacze przemieszczają się pomiędzy punktami. Z dowolnego punktu można się dostać do dowolnego innego punktu na 1 sposób, korzystając z 1 lub większej liczby lin poręczowych. Punkt numer 1 znajduje się na szczycie K2. U podnóża góry znajdują się te spośród punktów od 2 do n, do których doprowadzona jest tylko 1 lina poręczowa.

Pan Janusz twierdzi, że zdobył K2 w ostatniego sylwestra, bo chciał mieć lepszy widok na pokazy sztucznych ogni. Nasz bohater pamięta fragment trasy, który pokonał wchodząc na szczyt, składający się z k lin poręczowych. Konkretnie Pan Janusz pamięta grubość każdej z kolejnych k lin poręczowych.

Odpowiedz na pytanie, ile jest różnych fragmentów tras, prowadzących w kierunku szczytu, które odpowiadają fragmentowi trasy zapamiętanemu przez Pana Janusza? Dwa fragmenty trasy uznajemy za różne, jeżeli różnią się co najmniej 1 z punktów końcowych.

Wejście

W pierwszej linii wejścia znajdują się dwie liczby naturalne n ∈ [2, 105] i k ∈ [1, n - 1] oznaczających odpowiednio liczbę punktów na K2 oraz liczbę lin poręczowych we fragmencie trasy pokonanym przez naszego bohatera.

W kolejnych n - 1 liniach znajdują się opisy lin poręczowych. Opis każdej liny składa się z numerów punktów pomiędzy którymi poprowadzona jest lina poręczowa u, v (1 ≤ u, vn; uv) oraz jej grubości g ∈ [1, 109].

W ostatniej linii wejścia znajduje się k liczb naturalnych z przedziału [1, 109]. Są to grubości kolejnych lin poręczowych we fragmencie trasy zapamiętanym przez naszego bohatera.

Wyjście

W pierwszej linii wyjścia należy wypisać liczbę x będącą odpowiedzią na pytanie, ile jest różnych fragmentów tras, prowadzących w kierunku szczytu, które odpowiadają fragmentowi trasy zapamiętanemu przez Pana Janusza.

W każdej z kolejnych x linii należy wypisać parę numerów punktów pomiędzy którymi znajduje się fragment trasy odpowiadający fragmentowi trasy zapamiętanemu przez naszego bohatera. W ramach każdej pary w pierwszej kolejności wypisujemy numer punktu znajdującego się bliżej podnóża góry. Pary numerów punktów powinny być wypisane w kolejności rosnącej. Oznacza to, że para a1 a2 powinna zostać wypisana przed parą b1 b2 jeżeli a1 < b1 albo a1 = b1 i a2 < b2.

Przykład

Wejście:

14 2
14 5 8
3 8 9
5 13 9
1 8 4
14 1 6
9 11 3
2 8 5
5 10 8
10 12 5
6 2 1
10 7 3
11 3 8
4 11 3
3 8

Wyjście:

3
4 3
7 5
9 3

Wyjaśnienie do przykładu:

Fragmenty tras odpowiadające fragmentowi trasy zapamiętanemu przez Pana Janusza to:

  • Punkt 4 - Punkt 11 - Punkt 3
  • Punkt 7 - Punkt 10 - Punkt 5
  • Punkt 9 - Punkt 11 - Punkt 3

Dodane przez:Maciej Boniecki
Data dodania:2021-12-17
Limit czasu wykonania programu:0.5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM32-GCC COBOL D-CLANG D-DMD ELIXIR FANTOM GOSU GRV JS-MONKEY NIM OBJC OBJC-CLANG PICO RUST SCM qobi CHICKEN VB.NET

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