题目描述

某道题原本给定一张有向图，并要求输出任意两点之间的路径数量。但现在原输入文件丢失了，只剩下原程序的输出，也就是各点对之间的路径数量。

原图满足：

• 没有自环；
• 任意两个点之间至多有一条直接边；
• 图中不存在有向环。原题将这一性质描述为：若存在从 $u$ 到 $v$ 的路径，则不存在从 $v$ 到 $u$ 的路径。

现在给出所有“路径数大于 $0$”的有序点对以及对应路径数。未给出的点对之间路径数为 $0$。

你的任务是恢复原来的有向图。

题目保证输入数据对应一张合法的原图。

输入格式

第一行一个整数 $T$，表示测试数据组数：

每组数据第一行包含两个整数 $N,K$：

• $N$ 为点数，点编号为 $0,1,\ldots,N-1$；
• $K$ 为存在至少一条路径的有序点对数量。

接下来 $K$ 行，每行三个整数：

u v w

表示从点 $u$ 到点 $v$ 一共有 $w$ 条不同的有向路径，其中

没有在这 $K$ 行中出现的点对，其路径数为 $0$。

输出格式

对于第 $X$ 组数据，第一行输出：

Case X: N E

其中 $E$ 是恢复出的原图边数。

随后输出 $N$ 行。

第 $i$ 行先输出一个整数 $e_i$，表示从点 $i$ 直接连出的边数，然后按升序输出这 $e_i$ 个终点编号。

原题要求输出格式严格，不应有多余的前导、尾随空格。

样例

1
3 3
0 2 2
0 1 1
1 2 1

Case 1: 3 3
2 1 2
1 2
0