| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 10 | 3 | 3 | 37.500% |
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 ≤ T ≤ 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 ≤ N ≤ 300$, $0 ≤ M ≤ 10^6$).
In the next $M$ lines, there are two natural numbers $x$ and $y$ ($1 ≤ x, y ≤ 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 ≤ a, b, c ≤ 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 6
1 2 3
1 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 17
1 6 13 3 7 9 4 5 8