FRAKTAL - konkurs programistyczny

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, 10⁵] 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, v ≤ n; u ≠ v) oraz jej grubości g ∈ [1, 10⁹].

W ostatniej linii wejścia znajduje się k liczb naturalnych z przedziału [1, 10⁹]. 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 a₁ a₂ powinna zostać wypisana przed parą b₁ b₂ jeżeli a₁ < b₁ albo a₁ = b₁ i a₂ < b₂.

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