Перед началом решения задачи заметим, что у нас есть рёбра с приоритетами до $$$10^9$$$, поэтому необходимо провести сжатие приоритетов.

Для решения задачи будем использовать структуру данных DSU (Disjoint Set Union) с поддержкой количества компонент связности.

Для ответа на второй запрос воспользуемся DSU. Будем добавлять рёбра в DSU по возрастанию их приоритетов, пока не достигнем нужного количества компонент связности. Однако данное решение может привести к превышению лимита времени выполнения (TL).

Для оптимизации времени выполнения будем хранить $$$\sqrt{q}$$$ блоков DSU. В $$$k$$$-м блоке будем хранить DSU для рёбер с номерами от $$$1$$$ до $$$k\sqrt{q}$$$. Для ответа на второй запрос с помощью бинарного поиска найдем последний блок с количеством компонент связности больше необходимого. Пусть этот блок имеет номер $$$k$$$. Затем будем добавлять рёбра с приоритетами от $$$k\sqrt{q} + 1$$$ до $$$(k+1)\sqrt{q}$$$ в $$$k$$$-й блок, пока не достигнем нужного количества компонент связности. После этого откатим эти изменения.

Ассимптотика решения $$$O(q\sqrt{q})$$$