| Refact.ai Match 1 (Codeforces Round 985) |
|---|
| Закончено |
Вам дан неориентированный граф с $$$n$$$ вершинами и $$$m$$$ рёбрами.
Вы можете выполнить следующую операцию не более чем $$$2\cdot \max(n,m)$$$ раз:
- Выберите три различные вершины $$$a$$$, $$$b$$$ и $$$c$$$. Затем для каждого из рёбер $$$(a,b)$$$, $$$(b,c)$$$ и $$$(c,a)$$$ выполните следующее:
- Если ребро не существует, добавьте его. В противном случае, если оно существует, удалите его.
Граф называется классным, если и только если выполняется одно из следующих условий:
- Граф не имеет рёбер, или
- Граф является деревом.
Вам нужно сделать граф классным, выполняя указанные выше операции. Обратите внимание, что вы можете использовать не более чем $$$2\cdot \max(n,m)$$$ операций.
Можно показать, что всегда существует хотя бы одно решение.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$3\le n\le 10^5$$$, $$$0\le m\le \min\left(\frac{n(n-1)}{2},2\cdot 10^5\right)$$$) — количество вершин и количество рёбер.
Затем следуют $$$m$$$ строк, $$$i$$$-я строка содержит два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1\le u_i,v_i\le n$$$) — две вершины, которые соединяет $$$i$$$-е ребро.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^5$$$, а сумма $$$m$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.
Гарантируется, что в данном графе нет петель или кратных рёбер.
Для каждого набора входных данных в первой строке выведите целое число $$$k$$$ ($$$0\le k\le 2\cdot \max(n, m)$$$) — количество операций.
Затем выведите $$$k$$$ строк, $$$i$$$-я строка содержит три различных целых числа $$$a$$$, $$$b$$$ и $$$c$$$ ($$$1\le a,b,c\le n$$$) — три целых числа, которые вы выбрали в $$$i$$$-й операции.
Если существует несколько решений, вы можете вывести любое из них.
53 03 11 23 21 22 33 31 22 33 16 61 21 64 53 44 63 6
0 1 1 2 3 0 1 1 2 3 3 1 3 6 2 4 5 3 4 6
В первом наборе входных данных граф уже классный, потому что рёбер нет.
Во втором наборе входных данных, после выполнения единственной операции, граф становится деревом, поэтому он классный.
В третьем наборе входных данных граф уже классный, потому что он является деревом.
В четвёртом наборе входных данных, после выполнения единственной операции, граф не имеет рёбер, поэтому он классный.
В пятом наборе входных данных:
| Операция | Граф до операции | Граф после операции |
| $$$1$$$ |  |  |
| $$$2$$$ |  |  |
| $$$3$$$ |  |  |
Обратите внимание, что после первой операции граф уже стал классным, и есть две лишние операции. Поскольку граф по-прежнему классный после двух лишних операций, это является допустимым ответом.
