#P16125. [2026年山东集训一轮]构造题

[2026年山东集训一轮]构造题

题目描述

给定一个 nn 个点的完全图,边的颜色在 1∼m1\sim m 中,保证 m≥n−1m\ge n-1。

你需要新建 m−n+1m-n+1 个点和若干边,补全成一张 m+1m+1 个点的完全图,使得新图中每个点的临边颜色集恰好取遍 1∼m1\sim m。

也就是说,在补全后的完全图中,每个点连出的 mm 条边的颜色必须两两不同,并且恰好为 1,2,…,m1,2,\ldots,m。

输入格式

每个测试点有多组数据。

第一行一个正整数 TT,表示数据组数。

对于每组数据:

第一行两个正整数 n,mn,m。

接下来 n−1n-1 行,第 ii 行有 n−in-i 个正整数,其中第 jj 个表示边 (i,i+j)(i,i+j) 的颜色。

输出格式

对于每组数据:

首先输出一行 Yes 或 No,表示是否有解。

若有解,接下来输出 mm 行,第 ii 行有 m+1−im+1-i 个正整数,其中第 jj 个表示边 (i,i+j)(i,i+j) 的颜色。

你需要保证对于任意 1≤i<j≤n1\le i<j\le n,边 (i,j)(i,j) 的颜色与原图相同,即新图中的 1∼n1\sim n 号点与原图对应。

样例 1 输入

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

样例 1 输出

Yes
1 2 3 4 5
3 4 5 2
5 1 4
2 1
3
No

样例 2、3

见下发文件。

数据范围与约定

对于所有数据:

1≤n−1≤m≤200,1\le n-1\le m\le 200, 1≤T≤5.1\le T\le 5.
测试点编号 m≤m\le 特殊性质
1∼41\sim 4 4 无
5∼65\sim 6 200 n=1n=1
7∼97\sim 9 13 无
10∼1110\sim 11 50 m=nm=n
12∼1312\sim 13 无
14 100 m=nm=n
15∼1715\sim 17 无
18∼2018\sim 20 200