Обратите внимание на нестандартное ограничение по памяти в этой задаче.

Дан неориентированный граф из n вершин и m ребер. Вершины пронумерованы целыми числами от 1 до n, рёбра нумеруются целыми числами от 1 до m. Каждое ребро может быть покрашено в один из k цветов, которые нумеруются целыми числами от 1 до k. Изначально ни одно ребро не покрашено ни в один из цветов.

Вам приходят запросы вида «Перекрасьте ребро номер e_i в цвет c_i». В любой момент времени граф, образованный ребрами одного цвета, должен быть двудольным. Если после перекраски это условие нарушится, то запрос считается некорректным и ребро e_i сохраняет свой цвет. Иначе ребро e_i перекрашивается в цвет c_i, а запрос считается корректным.

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

Например, пусть дан граф-треугольник, то есть граф с тремя вершинами и ребрами (1, 2), (2, 3) и (3, 1). Пусть первые два ребра покрашены в цвет 1, а третье — в цвет 2. Тогда запрос «перекрасить третье ребро в цвет 1» будет некорректным, потому что после его исполнения граф, образованный ребрами цвета 1, не будет являться двудольным. С другой стороны, возможно перекрасить второе ребро в цвет 2.

Вам поступает q запросов. Для каждого запроса вы должны либо применить его, и сообщить, что запрос корректен, либо сообщить, что запрос некорректен.