\begin{tutorial}{Musaigen no Phantom World}

Перед началом решения задачи заметим, что у нас есть рёбра с приоритетами до $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})$

\end{tutorial}
