E1. Хеопс и контест (простая версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии $$$m$$$ равно $$$2$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

В Древнем Египте проходит соревнование по решению задач с $$$n$$$ участниками, пронумерованными от $$$1$$$ до $$$n$$$. Каждый участник представляет определенный город; города пронумерованы от $$$1$$$ до $$$m$$$. Из каждого города есть как минимум один участник.

У $$$i$$$-го участника есть сила $$$a_i$$$, специализация $$$s_i$$$ и мудрость $$$b_i$$$, при этом $$$b_i \ge a_i$$$. Каждая задача в соревновании будет иметь некоторую сложность $$$d$$$ и уникальную тему $$$t$$$. $$$i$$$-й участник решит задачу, если

  • $$$a_i \ge d$$$, т.е. его сила не меньше сложности задачи, или
  • $$$s_i = t$$$, и $$$b_i \ge d$$$, т.е. его специализация соответствует теме задачи, и его мудрость не меньше сложности задачи.

Хеопс хочет выбрать задачи таким образом, чтобы каждый участник из города $$$i$$$ решил строго больше задач, чем каждый участник из города $$$j$$$, для всех $$$i < j$$$.

Пожалуйста, найдите набор из не более чем $$$5n$$$ задач, где темы всех задач попарно различны, чтобы воля Хеопса была удовлетворена, или укажите, что это невозможно.

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

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

Первая строка содержит два целых числа $$$n$$$, $$$m$$$ ($$$2 \mathbf{=} m \le n \le 3 \cdot {10}^5$$$) — количество участников и количество городов.

Следующие $$$n$$$ строк описывают участников. $$$i$$$-я строка содержит три целых числа — $$$a_i$$$, $$$b_i$$$, $$$s_i$$$ ($$$0 \le a_i, b_i, s_i \le {10}^9$$$, $$$a_i \le b_i$$$) — силу, мудрость и специализацию $$$i$$$-го участника соответственно.

Следующие $$$m$$$ строк описывают города. В $$$i$$$-й строке первое число является целым $$$k_i$$$ ($$$1 \le k_i \le n$$$) — количество участников из $$$i$$$-го города. За ним следуют $$$k_i$$$ целых числа $$$q_{i, 1}, q_{i, 2}, \ldots, q_{i, k_i}$$$ — ($$$1 \le q_{i, j} \le n$$$, $$$1 \le j \le k_i$$$) — индексы участников из этого города. Гарантируется, что каждый участник упоминается ровно один раз.

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

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

Если существует набор задач, который удовлетворяет условиям Хеопса, то в первой строке выведите одно целое число $$$p$$$ ($$$1 \le p \le 5n$$$) — количество задач в вашем решении.

Затем выведите $$$p$$$ строк, каждая из которых содержит два целых числа $$$d$$$ и $$$t$$$ ($$$0 \le d, t \le {10}^9$$$) — сложность и тема соответствующей задачи. Темы должны быть различными.

Если нет набора задач, который соответствует желаниям Хеопса, выведите $$$-1$$$ вместо этого.

Пример
Входные данные
2
5 2
5 7 1
6 7 2
3 9 2
5 10 3
4 4 1
2 1 2
3 3 4 5
2 2
1 2 1
1 2 1
1 2
1 1
Выходные данные
7
6 4
6 5
5 6
5 7
4 8
4 9
7 1
-1