Вам дан неориентированный граф с \(n\) вершинами и \(m\) рёбрами.
Вы можете выполнить следующую операцию не более чем \(2\cdot \max(n,m)\) раз:
- Выберите три различные вершины \(a\), \(b\) и \(c\). Затем для каждого из рёбер \((a,b)\), \((b,c)\) и \((c,a)\) выполните следующее:
- Если ребро не существует, добавьте его. В противном случае, если оно существует, удалите его.
Граф называется классным, если и только если выполняется одно из следующих условий:
- Граф не имеет рёбер, или
- Граф является деревом.
Вам нужно сделать граф классным, выполняя указанные выше операции. Обратите внимание, что вы можете использовать не более чем \(2\cdot \max(n,m)\) операций.
Можно показать, что всегда существует хотя бы одно решение.
Выходные данные
Для каждого набора входных данных в первой строке выведите целое число \(k\) (\(0\le k\le 2\cdot \max(n, m)\)) — количество операций.
Затем выведите \(k\) строк, \(i\)-я строка содержит три различных целых числа \(a\), \(b\) и \(c\) (\(1\le a,b,c\le n\)) — три целых числа, которые вы выбрали в \(i\)-й операции.
Если существует несколько решений, вы можете вывести любое из них.
Примечание
В первом наборе входных данных граф уже классный, потому что рёбер нет.
Во втором наборе входных данных, после выполнения единственной операции, граф становится деревом, поэтому он классный.
В третьем наборе входных данных граф уже классный, потому что он является деревом.
В четвёртом наборе входных данных, после выполнения единственной операции, граф не имеет рёбер, поэтому он классный.
В пятом наборе входных данных:
| Операция | Граф до операции | Граф после операции |
| \(1\) |  |  |
| \(2\) |  |  |
| \(3\) |  |  |
Обратите внимание, что после первой операции граф уже стал классным, и есть две лишние операции. Поскольку граф по-прежнему классный после двух лишних операций, это является допустимым ответом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 0
3 1
1 2
3 2
1 2
2 3
3 3
1 2
2 3
3 1
6 6
1 2
1 6
4 5
3 4
4 6
3 6
|
0
1
1 2 3
0
1
1 2 3
3
1 3 6
2 4 5
3 4 6
|