시간 제한메모리 제한제출정답맞힌 사람정답 비율
15 초 2048 MB1000.000%

문제

This is an "output-only" problem. The test cases are made available to you. However, due to the large output size, you should still submit a program that reads the input and produces the outputs within the time limit.

Busy Beaver generated a random undirected graph with $N$ vertices and $M$ edges, where $M$ is a multiple of $3$. Now, he wants to partition the edges into $M/3$ paths of length $3$ (possibly starting and ending at the same vertex). Can you help Busy Beaver find such a partition?

입력

Please download the test data using this link.

The first line of input contains two integers $N$ and $M$ --- the number of vertices and edges in the graph, respectively.

The $i$th of the next $M$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i,v_i \le N, u_i \ne v_i$) --- the endpoints of the $i$th edge.

It is guaranteed that the $M$ edges were generated randomly. Formally, out of the $\frac{N(N-1)}{2}$ possible edges, $M$ distinct edges were chosen uniformly at random without replacement.

출력

Output $M/3$ lines. The $i$th line should contain $4$ integers $a_i$, $b_i$, $c_i$, and $d_i$ ($1 \le a_i,b_i,c_i,d_i \le N$), representing a path using edges $(a_i,b_i)$, $(b_i,c_i)$, and $(c_i,d_i)$.

It is allowed to have $a_i = d_i$. Your output should satisfy $$ \bigcup_{i=1}^{M/3} \{\{a_i,b_i\},\{b_i,c_i\},\{c_i,d_i\}\} = \bigcup_{i=1}^M \{\{u_i,v_i\}\}. $$

점수

There are $10$ test cases in total, each worth $10$ points. For your convenience, the values of $N$ and $M$ in each test case are shown in the following list:

  • Test $1$: $N = 771$, $M = 296835$.
  • Test $2$: $N = 772$, $M = 297606$.
  • Test $3$: $N = 1000$, $M = 300000$.
  • Test $4$: $N = 3000$, $M = 300000$.
  • Test $5$: $N = 10000$, $M = 300000$.
  • Test $6$: $N = 30000$, $M = 300000$.
  • Test $7$: $N = 50000$, $M = 300000$.
  • Test $8$: $N = 70000$, $M = 300000$.
  • Test $9$: $N = 80000$, $M = 300000$.
  • Test $10$: $N = 90000$, $M = 300000$.

It is guaranteed that each of the $10$ generated graphs has a valid partition.

예제 입력 1

10 15
3 10
10 4
3 6
5 8
10 9
5 2
1 4
1 9
1 7
8 3
1 6
6 10
10 2
8 2
4 3

예제 출력 1

2 5 8 2
8 3 10 2
3 4 1 7
6 1 9 10
3 6 10 4

노트

The sample is provided to illustrate the input and output format. It is not scored.

The sample graph and partition are shown in the figure below. Note that the path $2 - 5 - 8 - 2$ starts and ends at the same vertex, which is allowed.

채점 및 기타 정보

  • 100점 이상을 획득해야 를 받는다.
  • 예제는 채점하지 않는다.