Оценка на экспорт
Лука владеет компанией географических данных, которая ведет подробную карту города и экспортирует данные заинтересованным сторонам. Часто клиентам не нужна полная карта. Вместо этого им нужна упрощенная карта, содержащая только основные улицы.
Карта города представляет собой неориентированный граф, состоящий из 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-ое число t[k] (0 ≤ t[k] ≤ 300 000) является пороговым значением для k-го запроса.
Выходные данные
Выведите q строк. В k - ой строке выведите два целых числа - количество пересечений и количество улиц соответственно, на экспортированной карте для k - го запроса.