Problem1149--强连通入门3:牛场的婚礼

1149: 强连通入门3:牛场的婚礼

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 1
[Status] [Submit] [Creator:]

Description

 

【题目】
一个牛场有n只公牛,同时有n只母牛。
每只公牛都有自己喜欢的若干母牛。(一定存在完备匹配)
求每只公牛可以选择哪些母牛可以让剩下的每只公牛依旧能够选择到自己喜欢的一只母牛。
【输入格式】
第一行一个整数n(1 <= n <= 2000).
下来n行,每行第一个数ki表示第i只公牛喜欢的母牛数目,下来ki只母牛的编号。
所有ki的总和不超过 200000。

【输出格式】
   输出每只公牛可以匹配的母牛的编号(从小到大输出),且其他公牛和母牛依然一一匹配。
【样例输入】
4
2 1 2
2 1 2
2 2 3
2 3 4
【样例输出】
1 2
1 2
3
4

Source/Category