CF82B.Sets

普及+/提高

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Little Vasya likes very much to play with sets consisting of positive integers. To make the game more interesting, Vasya chose n non-empty sets in such a way, that no two of them have common elements.

One day he wanted to show his friends just how interesting playing with numbers is. For that he wrote out all possible unions of two different sets on n·(n - 1) / 2 pieces of paper. Then he shuffled the pieces of paper. He had written out the numbers in the unions in an arbitrary order.

For example, if n = 4, and the actual sets have the following form {1, 3}, {5}, {2, 4}, {7}, then the number of set pairs equals to six. The six pieces of paper can contain the following numbers:

  • 2, 7, 4.
  • 1, 7, 3;
  • 5, 4, 2;
  • 1, 3, 5;
  • 3, 1, 2, 4;
  • 5, 7.

Then Vasya showed the pieces of paper to his friends, but kept the n sets secret from them. His friends managed to calculate which sets Vasya had thought of in the first place. And how about you, can you restore the sets by the given pieces of paper?

小Vasya非常喜欢玩由正整数组成的集合。为了让游戏更有趣,Vasya精心选择了 nn 个非空集合,使得其中任意两个集合均无公共元素(即两两不相交)。

某天,他想向朋友们展示数字游戏究竟有多有趣。为此,他将所有可能的、由两个不同集合构成的并集写在了 n⋅(n−1)2\frac{n\cdot(n-1)}{2} 张纸上。接着,他将这些纸片彻底打乱顺序。在每张纸上,并集中各数字的书写顺序是任意的。

例如,若 n=4n = 4,而实际的四个集合为 {1, 3}\{1,\,3\}、{5}\{5\}、{2, 4}\{2,\,4\}、{7}\{7\},则集合对的总数为六对。这六张纸片上可能出现的数字如下:

  • 2, 7, 42,\,7,\,4;
  • 1, 7, 31,\,7,\,3;
  • 5, 4, 25,\,4,\,2;
  • 1, 3, 51,\,3,\,5;
  • 3, 1, 2, 43,\,1,\,2,\,4;
  • 5, 75,\,7。

随后,Vasya 将这些纸片展示给朋友们,却对自己的原始 nn 个集合严格保密。他的朋友们成功地推断出了 Vasya 最初想到的是哪 nn 个集合。那么你呢?你能仅根据所给的这些纸片,还原出原始的 nn 个集合吗?

输入格式

The first input file line contains a number n (2 ≤ n ≤ 200), n is the number of sets at Vasya's disposal. Then follow sets of numbers from the pieces of paper written on n·(n - 1) / 2 lines. Each set starts with the number k__i (2 ≤ k__i ≤ 200), which is the number of numbers written of the i-th piece of paper, and then follow k__i numbers a__ij (1 ≤ a__ij ≤ 200). All the numbers on the lines are separated by exactly one space. It is guaranteed that the input data is constructed according to the above given rules from n non-intersecting sets.

第一行输入文件包含一个数字 nn(2≤n≤2002 \leq n \leq 200),nn 表示瓦夏所拥有的集合数量。随后的 n⋅(n−1)2\frac{n \cdot (n-1)}{2} 行中,每行描述一张纸片上的数字集合。每个集合以数字 kik_i(2≤ki≤2002 \leq k_i \leq 200)开头,表示第 ii 张纸片上所写的数字个数,其后紧跟 kik_i 个数字 aija_{ij}(1≤aij≤2001 \leq a_{ij} \leq 200)。每行中的所有数字均恰好以一个空格分隔。保证输入数据严格遵循上述规则构造,即由 nn 个互不相交的集合生成。

输出格式

Print on n lines Vasya's sets' description. The first number on the line shows how many numbers the current set has. Then the set should be recorded by listing its elements. Separate the numbers by spaces. Each number and each set should be printed exactly once. Print the sets and the numbers in the sets in any order. If there are several answers to that problem, print any of them.

It is guaranteed that there is a solution.

在 n 行中输出瓦夏(Vasya)的集合描述。每行的第一个数字表示当前集合中元素的个数;随后按任意顺序列出该集合的所有元素,各数字之间用空格分隔。每个数字及每个集合均需恰好输出一次。集合之间以及集合内各数字之间的顺序可任意。若存在多种合法答案,输出任意一种即可。

题目保证存在解。

输入输出样例

  • 输入#1

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

    输出#1

    1 7 
    2 2 4 
    2 1 3 
    1 5
  • 输入#2

    4
    5 6 7 8 9 100
    4 7 8 9 1
    4 7 8 9 2
    3 1 6 100
    3 2 6 100
    2 1 2

    输出#2

    3 7 8 9 
    2 6 100 
    1 1 
    1 2
  • 输入#3

    3
    2 1 2
    2 1 3
    2 2 3

    输出#3

    1 1 
    1 2 
    1 3

输入解题思路,AI测评打分。不知道怎么写?

首页