레이팅 미적용An undirected graph with \(6 \cdot N\) vertices and \(M\) edges is given. An additional property of the graph is
that it can be partitioned into \(2 \cdot N\) disjoint triangles.
Find \(N\) disjoint triangles in the graph.
In the first line, there is a natural number \(T\) (\(1 \le T \le 100\)), which indicates the number of test cases.
This is followed by \(T\) blocks of data.
In the first line of each block, there are natural numbers \(N\) and \(M\) (\(1 \le N \le 300\), \(0 \le M \le 10^{6}\)).
In the next \(M\) lines, there are two natural numbers \(x\) and \(y\) (\(1 \le x\), \(y \le 6 \cdot N\)), which indicate that there
is an edge between vertices \(x\) and \(y\).
The sum of all values of \(N\) across all test cases will not exceed 300.
For each test case, output \(N\) lines, each line containing three natural numbers \(a\), \(b\), \(c\) (\(1 \le a\), b, \(c \le 6 \cdot N\)),
which indicate that the vertices \(a\), \(b\), and \(c\) form a triangle.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 13점 | \(M = 6 \cdot N\) |
2 | 18점 | \(N = 3\), \(T = 1\) |
3 | 18점 | \(N = 6\), \(T = 1\) |
4 | 71점 | No additional constraints. |
1
1 6
1 2
2 3
1 3
4 5
4 6
5 61 2 31
3 26
4 7
4 9
7 9
4 5
4 8
5 8
4 12
4 18
12 18
3 7
3 9
15 5
15 8
6 13
6 1
13 1
6 14
6 17
14 17
6 2
6 10
2 10
16 13
16 1
11 14
11 171 6 13
3 7 9
4 5 8