| Когнитивные технологии. Финал 2024 |
|---|
| Finished |
В далекой галактике существует загадочный мир, известный как «Призрачный мир». В этом мире существуют различные существа, называемые «Призрачными». Каждый Призрачный обладает уникальными способностями и приоритетом.
В центре Призрачного мира находится древнее дерево, известное как «Высший Разум». Это существо является связующим звеном для всех Призрачных. Каждый Призрачный представлен вершиной в графе, где ребра представляют собой связи между Призрачными.
Но связи между Призрачными не так просты, как кажется. Каждая связь имеет свой приоритет, который определяет силу и значимость этой связи. Чем выше приоритет, тем сильнее связь.
Изначально, между Призрачными нет никаких связей.
В Призрачном мире существуют два типа запросов, которые могут быть сделаны к Высшему Разуму:
1. Запрос на добавление связи: + $$$a$$$ $$$b$$$ $$$k$$$. Этот запрос добавляет новую связь между двумя Призрачными существами с приоритетом $$$k$$$. Благодаря этому запросу, новая связь будет создана между Призрачными существами $$$a$$$ и $$$b$$$ с приоритетом $$$k$$$.
2. Запрос на поиск минимального приоритета: ? $$$p$$$. Этот запрос позволяет найти минимальный неотрицательный приоритет $$$k$$$, при котором ребра с приоритетом меньше или равном $$$k$$$, образуют ровно $$$p$$$ компонент связности в графе Призрачного мира. Если такого приоритета не существует, выводится значение $$$-1$$$.
Таким образом, игрокам предстоит использовать эти запросы, чтобы управлять связями в Призрачном мире и находить определенное количество компонент связности с заданным приоритетом. Это поможет им раскрыть тайны и силу Призрачного мира, и, возможно, даже спасти его от опасности.
Первая строка входных данных содержит два целых числа $$$n$$$ — количество вершин и $$$q$$$ — количество запросов ($$$1 \leq n \leq 3000$$$, $$$0 \leq q \leq 10^5$$$)
Далее в следующих $$$q$$$ строчках идет описание запросов. Описание каждого запроса имеет следующий вид:
Выведите ответ на каждый запрос второго типа
6 12 + 1 2 1 + 1 3 3 + 2 3 7 + 4 5 2 + 5 6 4 ? 1 + 6 3 5 + 6 3 10 + 6 4 6 ? 6 ? 2 ? 1
-1 0 4 5
Итоговый граф в примере
| Name |
|---|


