Разбор добавил Иван Смирнов

Заметим, что количество запросов позволяет сначала считать их и сохранить, а потом решить задачу в офлайн-режиме. В таком случае удобнее решать задачу, считая, что запросы поступают в обратном порядке. Переформулируем ее в такой постановке: Дан пустой граф. Поступают запросы вида "добавить ребро (u, v)" и "определить, находятся ли вершины u и v в одной компоненте связности". Отвечать на такие запросы можно с помощью системы непересекающихся множеств (DSU). Введем систему непересекающихся множеств вершин. На запрос "cut u v" будем отвечать объединением множеств u и v, а на запрос "ask u v" - проверять, находятся ли вершины u и v в одном множестве или нет.