E. Запросы на индуцированных подграфах
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан неориентированный невзвешенный граф $$$G$$$ с $$$n$$$ вершинами и $$$m$$$ рёбрами. Граф $$$G$$$ не содержит петель и кратных рёбер.

Обозначим множество вершин графа $$$G$$$ как $$$V$$$. Для любого подмножества вершин $$$V' \subseteq V$$$ соответствующий индуцированный подграф, обозначаемый как $$$G[V']$$$, определяется следующим образом:

  • $$$G[V']$$$ — это граф, множество вершин которого равно $$$V'$$$, а множество рёбер состоит из всех рёбер в $$$G$$$, у которых оба конца находятся в $$$V'$$$.

Ваша задача — ответить на $$$q$$$ запросов. В каждом запросе даётся три целых числа $$$l$$$, $$$r$$$ и $$$k$$$. Обозначив $$$V'=\{l,l+1,\ldots,r\}$$$, вам нужно найти $$$k$$$-е по величине значение среди $$$f(l,G[V'])$$$, $$$f(l+1,G[V'])$$$, $$$\ldots$$$, $$$f(r,G[V'])$$$ (т.е. $$$k$$$-е значение в порядке возрастания; повторяющиеся значения считаются несколько раз).

Здесь $$$f(u,G[V'])=\bigoplus_{(u,v)\in G[V']}v$$$. Другими словами, это побитовый XOR значений меток всех соседних вершин вершины $$$u$$$ в графе $$$G[V']$$$.

Для лучшего понимания условия обратитесь к примечаниям к примеру.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1.5 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 1.5 \cdot 10^5$$$, $$$1 \leq m \leq 1.5 \cdot 10^5$$$) — количество вершин и рёбер соответственно.

Следующие $$$m$$$ строк содержат по два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$), представляющих неориентированное ребро между вершинами $$$u_i$$$ и $$$v_i$$$.

Следующая строка содержит одно целое число $$$q$$$ ($$$1 \leq q \leq 1.5 \cdot 10^5$$$) — количество запросов.

Каждая из следующих $$$q$$$ строк содержит по три целых числа $$$l$$$, $$$r$$$ и $$$k$$$ ($$$1 \leq l \leq r \leq n$$$, $$$1 \le k \le r-l+1$$$), определяющих запрос на индуцированном подграфе $$$G[\{l,\ldots,r\}]$$$.

Гарантируется, что граф не содержит петель и кратных рёбер.

Гарантируется, что каждая из сумм $$$n$$$, $$$m$$$ и $$$q$$$ по всем наборам входных данных не превосходит $$$1.5 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$q$$$ целых числа — ответы на каждый запрос.

Пример
Входные данные
2
4 5
1 3
1 4
2 3
2 4
3 4
3
1 2 2
1 3 1
2 4 3
2 1
2 1
3
1 1 1
2 2 1
1 2 2
Выходные данные
0
3
7
0
0
2
Примечание

В первом наборе входных данных входной граф $$$G$$$ представлен на следующем рисунке.

Данный граф $$$G$$$.

Для первого запроса индуцированный подграф $$$G[\{1,2\}]$$$ представлен на следующем рисунке. Мы видим, что вершины $$$1$$$ и $$$2$$$ не имеют соседних вершин. Таким образом, $$$f(1,G[\{1,2\}])=f(2,G[\{1,2\}])=0$$$. $$$2$$$-е по величине значение равно $$$0$$$.

$$$G[\{1,2\}]$$$.

Для второго запроса индуцированный подграф $$$G[\{1,2,3\}]$$$ представлен на следующем рисунке. Мы видим, что $$$f(1,G[\{1,2,3\}])=3$$$, $$$f(2,G[\{1,2,3\}])=3$$$, и $$$f(3,G[\{1,2,3\}])=1 \oplus 2=3$$$. $$$1$$$-е по величине значение равно $$$3$$$.

$$$G[\{1,2,3\}]$$$.

Для третьего запроса индуцированный подграф $$$G[\{2,3,4\}]$$$ представлен на следующем рисунке. Мы видим, что $$$f(2,G[\{2,3,4\}])=3 \oplus 4=7$$$, $$$f(3,G[\{2,3,4\}])=2 \oplus 4=6$$$, и $$$f(4,G[\{2,3,4\}])=2 \oplus 3=1$$$. $$$3$$$-е по величине значение равно $$$7$$$.

$$$G[\{2,3,4\}]$$$.