Оцінка на експорт

Лука володіє компанією, що спеціалізується на географічних даних, і створює детальні карти міста для експорту зацікавленим клієнтам. Часто клієнтам не потрібна повна карта, а лише спрощена версія, що включає лише основні вулиці.

Карта міста представлена у вигляді неорієнтованого графа, що складається з $n$ перехресть, позначених цілими числами від $1$ до $n$, і $m$ двосторонніх вулиць. Кожна вулиця має пріоритет, виражений невід'ємним цілим числом. Коли клієнт запитує карту, він обирає пороговий пріоритет $p$. Оригінальна карта копіюється і перетворюється в експортовану карту за наступною процедурою:

1. Видаляються всі вулиці з пріоритетом нижче $p$.

2. Для кожного перехрестя $i$ від $1$ до $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$ однакові).

За наданою картою і послідовністю запитів на експорт, для кожного запиту визначте кількість перехресть і кількість вулиць на експортованій карті.