시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 1024 MB103337.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.

서브태스크

번호배점제한
113

$M = 6 \cdot N$

218

$N = 3$, $T = 1$

318

$N = 6$, $T = 1$

471

No additional constraints.

예제 입력 1

1
1 6
1 2
2 3
1 3
4 5
4 6
5 6

예제 출력 1

1 2 3

예제 입력 2

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

예제 출력 2

1 6 13
3 7 9
4 5 8

채점 및 기타 정보

  • 예제는 채점하지 않는다.