Обратите внимание на нестандартное ограничение по памяти в этой задаче.
Дан неориентированный граф из n вершин и m ребер. Вершины пронумерованы целыми числами от 1 до n, рёбра нумеруются целыми числами от 1 до m. Каждое ребро может быть покрашено в один из k цветов, которые нумеруются целыми числами от 1 до k. Изначально ни одно ребро не покрашено ни в один из цветов.
Вам приходят запросы вида «Перекрасьте ребро номер ei в цвет ci». В любой момент времени граф, образованный ребрами одного цвета, должен быть двудольным. Если после перекраски это условие нарушится, то запрос считается некорректным и ребро ei сохраняет свой цвет. Иначе ребро ei перекрашивается в цвет ci, а запрос считается корректным.
Напомним, что граф называется двудольным, если множество его вершин можно разбить на две части так, чтобы ни одно ребро не соединяло вершины из одной и той же части.
Например, пусть дан граф-треугольник, то есть граф с тремя вершинами и ребрами (1, 2), (2, 3) и (3, 1). Пусть первые два ребра покрашены в цвет 1, а третье — в цвет 2. Тогда запрос «перекрасить третье ребро в цвет 1» будет некорректным, потому что после его исполнения граф, образованный ребрами цвета 1, не будет являться двудольным. С другой стороны, возможно перекрасить второе ребро в цвет 2.
Вам поступает q запросов. Для каждого запроса вы должны либо применить его, и сообщить, что запрос корректен, либо сообщить, что запрос некорректен.
Выходные данные
Для каждого запроса выведите «YES» (без кавычек), если он корректен, либо «NO» (без кавычек), если этот запрос нарушит двудольность графа, образованного ребрами какого-либо цвета.