Оценка на экспорт
Оценка на экспорт
Лука владеет компанией географических данных, которая ведет подробную карту города и экспортирует данные заинтересованным сторонам. Часто клиентам не нужна полная карта. Вместо этого им нужна упрощенная карта, содержащая только основные улицы.
Карта города представляет собой неориентированный граф, состоящий из n пересечений, обозначенных целыми числами от 1 до n и m двухсторонних улиц. Каждой улице присваивается приоритет - неотрицательное целое число. При запросе карты клиент выбирает пороговый приоритет p. Затем исходная карта копируется и преобразуется в экспортированную карту, используя следующую процедуру:
Все улицы, приоритет которых ниже p, удаляются.
Для каждого пересечения i для 1, 2, . . . , n (обрабатываются в указанном порядке):
(a) Если пересечение i не соединено ни с одной из улиц, то оно удаляется.
(b) Если пересечение i соединено только с двумя улицами x и y, ведущих к пересечениям a и b отличных от i, тогда пересечение i стягивается следующим образом:
- улицы x и y удаляются.
- Пересечение i удаляется.
- Добавляется новая улица z, соединяющая пересечения a и b.
Иллюстрация второго примера с пороговым приоритетом 95
Изначально карта не содержит петель (петля - это улица, которая соединяет пересечение с самим собой) и параллельных ребер (более одной улицы между одной и той же парой пересечений), но петли и параллельные ребра могут образовываться во время процедуры сжатия. Обратите внимание, что на шаге 2. (б) выше ни x, ни y не могут быть петлями (оба a и b должны отличаться от i), Но вновь добавленная улица z может быть петлей (возможно a и b одинаковы).
По заданной карте и последовательности входящих запросов на экспорт, для каждого запроса найдите количество пересечений и количество улиц на экспортируемой карте.
Входные данные
Первая строка содержит два числа n (1 ≤ n ≤ 300 000) и m (1 ≤ m ≤ 300 000) – количество пересечений и количество улиц. Каждая из следующих m строк содержит три целых числа a, b и p (1 ≤ a, b ≤ n, 0 ≤ p ≤ 300 000), описывающих улицу с приоритетом p соединяющую перекрестки a и b. Никакая улица не соединяет перекресток сам с собой. Между каждой парой перекрестков существует не более одной улицы.
Следующая строка содержит количество запросов на єкспорт q (1 ≤ q ≤ 300 000). Следующая строка содержит q целых чисел. k-ое число tk
(0 ≤ tk
≤ 300 000) является пороговым значением для k-го запроса.
Выходные данные
Выведите q строк. В k - ой строке выведите два целых числа - количество пересечений и количество улиц соответственно, на экспортированной карте для k - го запроса.
6 7 1 2 20 2 3 80 2 5 100 3 5 50 3 4 100 5 6 90 4 6 100 4 25 75 85 95
2 3 1 1 2 1 4 2
10 14 2 7 150 1 2 100 2 3 150 3 1 200 1 4 60 4 5 20 2 5 100 5 6 90 6 7 120 7 5 130 6 8 50 8 9 200 9 10 200 10 7 200 5 300 50 95 100 110
0 0 6 9 4 5 4 5 5 4