Effective Role Privileges

There are n roles numbered 0..n−1, and role i has a set of direct permissions. A grant [u, v] means role v inherits all permissions of role u. Inheritance is transitive, and the grants form a directed acyclic graph.

The effective permissions of a role are its own direct permissions plus the direct permissions of all its ancestor roles. For each role, find its deduplicated effective permissions sorted in ascending lexicographic order.

输入格式

The first line contains two integers n and m. Each of the next n lines describes one role: line i starts with an integer k, followed by the k direct permission strings of role i−1 (duplicates are possible, and k may be 0). Each of the next m lines contains two integers u v, meaning role v inherits role u.

1≤n≤2000, 0≤m≤200000, and the sum of all k is at most 200000; 0≤u,v<n, the grant graph is acyclic, and the same grant may appear more than once. A permission string has length 1..10, consists of visible ASCII characters (33..126), and contains no spaces; there are at most 2000 distinct permission strings.

输出格式

Output n lines; line i corresponds to role i−1: first output the number of effective permissions c, then output the c distinct permission strings in lexicographic (ASCII) order, separated by spaces.

样例 1

输入：

3 2
1 A
1 B
1 C
0 1
1 2

输出：

1 A
2 A B
3 A B C

样例 2

输入：

4 3
1 READ
1 WRITE
1 DEPLOY
1 AUDIT
0 2
1 2
2 3

输出：

1 READ
1 WRITE
3 DEPLOY READ WRITE
4 AUDIT DEPLOY READ WRITE

样例 3

输入：

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

输出：

1 A
1 A
1 A

样例说明

Example 1: role 1 inherits role 0, and role 2 inherits role 0 indirectly through role 1, so the effective permissions are {A}, {A,B}, and {A,B,C}. Example 2: role 2 inherits both roles 0 and 1, and role 3 inherits role 2, so it gets all four permissions. Example 3: the direct permission A of role 0 appears more than once and is kept only once after deduplication; role 2 has no direct permissions but inherits A.