Aho-Corasick 算法接收一组字符串作为输入，我们将其称为字典。然后它会构建以下结构：

字典中每个字符串的所有前缀都对应一个顶点。此外，还有一个对应空字符串的顶点。由这组顶点构成了两棵树。

第一棵树称为 trie（字典树），它由所有对应字符串 $s$ 和 $t$ 的节点之间的边组成，其中 $t$ 可以通过在 $s$ 后附加单个字符得到。

第二棵树称为 suffix links（后缀链接），它由所有对应不同字符串 $s$ 和 $t$ 的节点之间的边组成，其中 $s$ 是 $t$ 的后缀，且不存在与 $s$ 和 $t$ 不同的字符串 $w$ 对应一个 trie 节点，使得 $s$ 是 $w$ 的后缀且 $w$ 是 $t$ 的后缀。

可以证明，trie 和后缀链接都是树。在本题中，所有边都是无向的。在本题中，树被视为边的集合，边被视为顶点的无序对。给定同一顶点集 $S$ 上的两棵树 $A$ 和 $B$，请构造一个字典，使得：

1. 将 Aho-Corasick 算法应用于该字典所生成的树与给定的树同构。换句话说，令 $V$ 表示构建的 trie 和后缀链接的节点（顶点）集合，$T$ 表示构建的 trie，$L$ 表示后缀链接。必须存在一个双射 $f : S \to V$，使得 $\forall c_1, c_2 \in S, \{c_1, c_2\} \in A \iff \{f(c_1), f(c_2)\} \in T$ 且 $\{c_1, c_2\} \in B \iff \{f(c_1), f(c_2)\} \in L$。
2. 字典中所有字符串的总长度不超过 $3 \cdot 10^5$。

字母表大小受限于所有字符串的总长度。保证答案存在。

注意，存在某些树对，使得可以构造出一个满足第一个要求的字典，但无法同时满足两个要求。然而，本题不包含此类测试用例，因为保证答案存在。换句话说，第二个要求是有意义的。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 10^5$)，表示顶点数。

接下来 $n-1$ 行描述 trie。第 $i$ 行包含两个整数 $a$ 和 $b$，表示顶点 $a$ 和 $b$ 之间有一条边 ($1 \le a, b \le n$)。

接下来 $n-1$ 行以相同格式描述后缀链接。

保证 trie 和后缀链接均为树，且答案存在。

输出格式

第一行应包含一个整数 $k$ ($1 \le k \le 3 \cdot 10^5$)，表示字符串的数量。

接下来 $k$ 行包含这些字符串。每行应以一个整数 $l$ ($1 \le l \le 3 \cdot 10^5$) 开头，表示字符串长度。随后是 $l$ 个整数 $a_i$ ($1 \le a_i \le 3 \cdot 10^5$)，代表字符串的字符。相同的 $a_i$ 对应相同的字符，反之亦然。

所有字符串的总长度不应超过 $3 \cdot 10^5$。

样例

样例输入 1

2
1 2
2 1

样例输出 1

1
1 228

样例输入 2

3
1 2
2 3
3 2
2 1

样例输出 2

2
1 1
1 2

样例输入 3

3
1 2
2 3
2 1
3 2

样例输出 3

1
2 1 1

样例输入 4

3
1 2
2 3
3 1
3 2

样例输出 4

2
2 1 2
1 1

样例输入 5

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

样例输出 5

2
2 1 2
1 2

样例输入 6

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

样例输出 6

2
1 2
3 1 2 3

样例输入 7

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

样例输出 7

3
1 1
2 2 1
3 3 2 1