SP1483 PT07G - Colorful Lights Party

ACRush 和他的朋友们想为 THU 在 2007 年 ICPC 中取得的好成绩举办一场派对。他们计划使用 THU 的所有大厅来举办这场派对。这些大厅分为两种类型：小型大厅和大型大厅。每个大厅都配有一个以树形结构布置的电子灯光系统，这样可以减少多余的电线。 - 小型大厅中的灯光系统是一个有 $n$ 盏灯的普通树。这些灯的编号从 $1$ 到 $n$。 - 大型大厅中的灯光系统由 $k$ 条灯链组成，每条灯链的长度为 $t$。这些链的首灯与舞台中央的大灯相连。大灯的编号为 $1$，每条链的第一盏灯编号依次为 $2$ 到 $k+1$，然后继续为每条链的第二盏灯编号，以此类推。 请参考下图：  ACRush 希望在每个大厅中，每盏灯的颜色都是独特的，并且连接灯的电线颜色也要唯一。 为方便记忆和挂灯，他制定了如下规则： - 在每个大厅内，颜色编号从 $0$ 到 $n-1$，每盏灯都将获得一个独特的颜色编号，编号范围在 $\{0, 1, \ldots, n-1\}$。 - 连接第 $i$ 盏灯和第 $j$ 盏灯的电线的颜色编号由这两盏灯的颜色编号的正差值唯一确定。 乍一看，这个规则似乎很简单，大家都很支持它。但是，当房间较大时，给灯设置颜色变得非常棘手。几秒钟后，ACRush 说：「所以在这个大厅里，第 $1$ 盏灯应该是颜色 $3$，第 $2$ 盏灯应该是颜色 $0$，……」。他是怎么这么快速决定的？ 你能做到吗？请编写一个程序来帮助 ACRush 的朋友们为所有 $T$ 个大厅中的灯快速设置颜色。

第一行是整数 $T$，表示 THU 中的大厅数量（$0 < T \leq 10$）。接下来是一行空白。然后是关于 $T$ 个大厅的详细描述。 对于每个大厅，第一行包含一个整数 $kind$，表示当前大厅的类型：$1$ 表示小型大厅，$2$ 表示大型大厅。接下来的内容根据类型有所不同： - 对于类型 $1$（小型大厅），首先读入一个整数 $n$（$1 \leq n \leq 27$），表示灯的数量。接下来的 $n - 1$ 行描述了大厅内的电线连接情况，每行是一个对 $(u, v)$，表示灯 $u$ 和灯 $v$ 之间有一条电线（$1 \leq u, v \leq n$）。 - 对于类型 $2$（大型大厅），只有一行，包含两个整数 $k$ 和 $t$（$1 \leq k, t \leq 1000$），分别表示链的数量和每条链的长度。 每个大厅描述之后有一行空白。

对于每个大厅，输出一行包含 $n$ 个数字，第 $i$ 个数字表示第 $i$ 盏灯的颜色编号。如果有多个方案，任意一个都可以接受。如果没有可行方案，那么输出 $-1$。每行中的颜色编号用一个空格分隔，确保无多余空格。不同案例之间不需要空行。 ## 提示 - $0 < T \leq 10$ - 小型大厅的灯数量 $1 \leq n \leq 27$ - 大型大厅的链数量和链长 $1 \leq k, t \leq 1000$ **本翻译由 AI 自动生成**