eolymp
bolt
Try our new interface for solving problems
Məsələlər

Государственные дороги

Государственные дороги

Zaman məhdudiyyəti 5 saniyə
Yaddaşı istafadə məhdudiyyəti 512 MiB

В средние века на территории Байтландии существовало несколько государств. При этом границы государств постоянно изменялись, в результате чего крупные города переходили из одного государства в другое. Сейчас историки пытаются выяснить конфигурацию государств в разное время.

Один из применяемых ими способов основывается на упоминании в хрониках статуса соединяющих города дорог. Если в какой-то исторический момент дорога имеет статус государственной, то историки считают, что соединяемые ею города в этот момент точно принадлежат одному и тому же государству. Однако для передвижения использовались и дороги местного значения, о которых хроники даже не упоминают. Поэтому утверждение о том, что любые два города в одном государстве соединены государственной дорогой, в общем случае неверно, равно как и утверждение, что между любыми двумя городами, принадлежащими одному государству, можно было проехать исключительно по государственным дорогам.

Для проверки этого подхода историкам нужна система, сохраняющая данные о статусе дорог в хронологическом порядке и отвечающая на запросы относительно того, возможно ли, что в текущий (с точки зрения внутренней хронологии системы) момент заданные города - и только они - образовывали единое государство.

Giriş verilənləri

Первая строка ввода содержит два целых числа n и q (1n1000000, 1q2000000) - количество городов в средневековой Байтландии и количество событий (записей в хрониках и запросов). Города занумерованы последовательными целыми числами от 1 до n.

Далее идут события и запросы, перечисленные в хронологическом порядке (запрос относится к тому моменту времени, когда произошли все перечисленные до него события, но не произошло ни одного события, перечисленного после него). Каждая из q строк обозначает событие или запрос и имеет следующий формат:

  • "1 u v" (событие первого типа) обозначает, что дорога между городами u и v получила статус государственной (1u < vn);

  • "2 m" (событие второго типа) обозначает, что дорога, которая получила статус государственной в результате m-го с начала хроник события первого типа, перестала быть таковой (m может принимать значения от 1 до количества событий первого типа, произошедших перед данным);

  • "3 k u_1 u_2 ... u_k" - запрос: могло ли на момент, описываемый всеми уже обработанными событиями, существовать государство, список городов которого состоял из k городов с номерами {u_1, u_2, ..., u_k} (1k n, 1u_1 < u_2 < ... < u_kn).

На всех упоминаемых в хрониках дорогах движение является двусторонним, при этом любые два различных города соединены не более чем одной дорогой.

На момент инициализации базы (до первого запроса) ни одна дорога не имела статуса государственной. Одна и та же дорога может менять статус с государственной на обычную и наоборот сколько угодно раз. Гарантируется, что каждое m встретится в событиях второго типа не более одного раза. Сумма всех значений k не превосходит 2000000.

Çıxış verilənləri

В ответ на каждый запрос выведите в отдельной строке "YES" в случае, если данный список городов мог быть полным списком городов некоторого государства в соответствующий момент, и "NO" в противном случае.

Nümunə

Giriş verilənləri #1
4 10
3 3 1 3 4
1 1 2
3 3 1 3 4
1 2 3
3 2 1 3
3 3 1 2 3
1 3 4
1 2 4
2 1
3 3 2 3 4
Çıxış verilənləri #1
YES
NO
NO
YES
YES
Mənbə Yandex.Algorithm, Online Round 1, July 14, 2013