题目背景

本题征集 SPJ 和数据。

题目描述

给定一棵含 $n$ 个节点的树，节结点编号为 $1$ 到 $n$。

树上有 $m$ 只妖精，每个妖精有一个行走路线，能用一个长度为 $x$ 的序列 $a$ 表示。妖精会从结点 $a_1$ 开始，沿这样的路径行走：$a_1\to a_2 \to\cdots\to a_x\to a_1\to\cdots$。其中 $u\to v$ 代表沿 $u$ 到 $v$ 的简单路径行走。保证 $a$ 序列相邻两个元素不相同。

现在，灵梦想要进行妖精退治。每秒一只妖精会走一步，她也会走一步。

试着构造长度为 $l$ 的序列 $b$，使得灵梦沿这样的路径行走：$b_1\to b_2 \to\cdots\to b_l\to b_1\to\cdots$，在 $9961^{9961^{9961}}$ 秒内可以退治所有妖精。如果某一秒灵梦和某妖精在同一结点或同时经过了一条边则可以退治她。

保证给定的树由给定的随机树生成器生成。但是不保证路径为随机生成的。

灵梦希望你构造的 $l \leq 60$。

$1 \leq n \leq 300$

输入格式

第一行输入一个正整数 $T$，表示数据组数。对于每一组数据：

第一行输入三个正整数 $n,m,seed$，表示树的节点数、妖精个数和随机种子。

第二行开始往下 $m$ 行，每行首先输入一个正整数 $s$，表示第 $i$ 个妖精的路径节点数。接着输入 $s$ 个正整数 $a_{i,1},a_{i,2},\dots,a_{i,s}$，表示第 $i$ 个妖精的路径。

树将由给定的随机树生成器生成：

namespace Gen {
	mt19937 rnd;
	int pos[MAXN], deg[MAXN];
	vector <pair<int, int>> edges;
	void calc() {
		for (int i = 1; i <= n - 2; ++i)
			++deg[pos[i]];
		set <int> ret;
		ret.clear();
		for (int i = 1; i <= n; ++i)
			if (deg[i] == 1)
				ret.insert(i);
		for (int i = 1; i <= n - 2; ++i) {
			int npos = *ret.begin();
			edges.push_back(make_pair(npos, pos[i]));
			ret.erase(ret.begin());
			--deg[pos[i]];
			if (deg[pos[i]] == 1)
				ret.insert(pos[i]);
		}
		edges.push_back(make_pair(*ret.begin(), n));
	}
	void build() {
		for (auto i : edges) {
			int u = i.first, v = i.second;
			e[u].push_back(v);
			e[v].push_back(u);
		}
	}
	void generate(int seed) {
		rnd.seed(seed);
		edges.clear();
		for (int i = 1; i <= n; ++i)
			deg[i] = 1;
		for (int i = 1; i <= n - 2; ++i)
			pos[i] = rnd() % n + 1;
		calc();
		build();
	}
}

调用方法：在程序中调用 Gen::generate(seed) 即可生成一棵树且存在邻接表 vector <int> e[MAXN] 中。请在 -std=c++11 或者更高的语言标准下运行。

输出格式

对于每一组数据，输出一行，若干个整数，表示长度为 $l$ 的序列 $b$。

1
25 4 623532
3 11 3 5
5 24 17 15 19 17
6 14 21 16 8 18 21
8 21 18 17 19 24 21 24 17

19 24 17 15 8 16 21 14 19 8 19 13

提示

【样例解释】

根据样例中的随机种子可以构造如图的树：

显然可证 $\texttt{19 24 17 15 8 16 21 14 19 8 19 13}$ 是一个可以退治所有妖精的节点序列。