| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 15 초 | 2048 MB | 1 | 0 | 0 | 0.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:
It is guaranteed that each of the $10$ generated graphs has a valid partition.
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
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.
University > MIT > M(IT)^2 > M(IT)^2 Winter 2025 Tournament > Advanced Round 2 4번