一座大型博物馆里充满了华丽的房间和闪亮的走廊。由于它太大了，规划任何游览路线都成了一个严重的问题。这就是需要你提供帮助的地方。你需要帮助规划一些标识，使整个建筑中的导航变得更加容易。

其基本想法是：如果一个房间有 $d$ 个门，通过走廊通往其他房间，那么这些门和相应的走廊将在本地被标记为数字 $1, 2, \dots, d$。然后，建议所有游客遵循一个简单的规则：

• 如果游客在游览刚开始时处于房间 $v$，他们应该选择标记为 $1$ 的门并穿过相应的走廊。
• 如果游客在房间 $v$，且他们是通过标记为 $i$ 的门进入该房间的，他们应该选择标记为下一个数字的门（即如果 $i < d$ 则选择 $i + 1$，如果 $i = d$ 则选择 $1$）并穿过相应的走廊。

这里有一个简单的例子，游客从房间 1 开始，按顺序访问房间 1, 2, 3, 4, 5, 6，且每个走廊至少通过一次：

博物馆中的展品不仅展出在房间里，还展出在连接不同房间的走廊中。毕竟，走廊非常适合展示画作和摄影作品！因此，我们希望确保遵循规则的游客至少会通过每条走廊一次——假设他们不会轻易感到厌倦且步行时间足够长，无论他们是从哪个房间开始游览的。你的任务就是找到这样一种标记方案。

已知每个房间最多有 3 条向外延伸的走廊，且整个博物馆是连通的，即可以在任意两个房间之间走动（中途可能经过其他房间）。从单个房间出发的所有走廊都通往不同的房间。

输入格式

输入包含多个测试用例。第一行包含测试用例的数量 $t$ ($t \le 100$)。

每个测试用例以一行开始，包含房间的数量 $n$ ($3 \le n \le 10^5$)。

接下来的 $n$ 行包含所有走廊的描述。其中第 $i$ 行描述了与第 $i$ 个房间相连的走廊。它以一个整数 $d$ ($1 \le d \le 3$) 开始，表示该房间的门数。随后是 $d$ 个整数 $r_1, r_2, \dots, r_d$，表示这些门所通往的房间编号（$1 \le r_j \le n$，且当 $j \ne k$ 时 $r_j \ne r_k$，以及 $r_j \ne i$）。

所有走廊都是双向的，因此如果有一扇门从房间 $x$ 通往房间 $y$，那么也有一扇门从房间 $y$ 通往房间 $x$。

输入文件的总大小不会超过 50MB。

输出格式

对于每个测试用例，输出恰好 $n$ 行。其中第 $i$ 行应包含与房间 $i$ 直接相连的房间编号，按其分配的标签顺序排列（格式与输入相同，即先输出通道数 $d$，然后按标签 $1, 2, \dots, d$ 的顺序输出相邻房间编号）。

你可以假设总是存在一种有效的门标记方案，你只需要找到其中一种即可。

样例

输入 1

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

输出 1

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