시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 2 | 1 | 1 | 50.000% |
You are given an undirected complete graph with $n$ vertices, where $n$ is odd. You need to partition its edge set into $k$ disjoint simple paths, satisfying that the $i$-th simple path has length $l_i$, and each undirected edge is used exactly once. The given lengths $l_i$ are integers from $1$ to $n - 3$.
A complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A simple path is a path where vertices are pairwise distinct. The length of a path is the number of edges in it.
It can be shown that an answer always exists if $\displaystyle \sum\limits_{i=1}^k l_i = \frac{n(n-1)}{2}$ holds.
The first line contains an integer $T$ ($1 \leq T \leq 10^5$), the number of test cases. Then $T$ test cases follow.
The first line of each test case contains two integers $n$ and $k$ ($5 \leq n \leq 1000$, $1 \leq k \leq \frac{n(n - 1)}{2}$, $n$ is odd), the number of vertices and paths, respectively. The second line contains $k$ integers $l_1, l_2, \ldots, l_k$ ($1 \le l_i \le n - 3$), the required lengths of the paths.
It is guaranteed that $\displaystyle \sum\limits_{i = 1}^{k} l_i = \frac{n(n - 1)}{2}$ holds for each test case.
It is also guaranteed for the total number of edges over all test cases that $\displaystyle \sum \frac{n(n - 1)}{2} \leq 10^6$.
For each test case, start by printing one line containing "Case #x:
", where $x$ ($1 \leq x \leq T$) is the test case number. Then output $k$ lines. In the $i$-th of these lines, print $l_i + 1$ integers denoting the vertices of the $i$-th path in order of traversal.
If there are multiple answers, print any one of them.
3 5 6 2 1 1 2 2 2 7 8 1 1 4 3 4 1 3 4 5 10 1 1 1 1 1 1 1 1 1 1
Case #1: 5 4 2 2 3 5 1 2 1 4 3 5 2 1 3 4 Case #2: 6 7 1 3 6 5 1 2 3 7 1 4 2 1 6 4 7 5 7 3 2 6 3 5 3 4 5 2 7 Case #3: 5 3 5 2 4 3 1 5 1 3 2 3 4 2 4 1 1 2 4 5