2013
12-30

# Games R Us

GamesAreUs.com has just completed its outside audit for this year. One item that was caught was the lack of any business rules for assigning permissions to files on the company’s shared file server. The analysts are working on setting up some roles for all employees and what permissions should be given to each role. Your team is to take a look at the existing situation so you can provide some input to the analysts.

Fortunately permission assignment has not been completely random. The most common way to set up a new employee is to ask that they be set up "just like Joe", effectively making an ad-hoc prototype system.

You will be given the access control lists (ACLs) for the top level directories of the shared file server. Using these, your team is to write a program to split the users up into equivalence classes where all members of a class have access to exactly the same directories.

Because of the several departments in GamesAreUs.com, there are multiple access control lists to be processed: one set of lists per department.

The first line of input to your program is a single integer n (0 < n < 100), by itself on the line without any white space, giving the number of departments. Following that are the data for those departments.

ACLs associated with one department is a sequence of ACLs ended by "-1" by itself. Each ACL is a line of unsigned integers (1 <= x <= 2147483647) separated from each other by a single blank. The first integer on the line is the file id (FID) of the directory. The remaining numbers on the line are the user ids (UIDs) that have access. Each line will have a FID and at least one UID. There will be no duplicate UIDs on the line, but note the UIDs and FIDs are in separate spaces so a UID could be the same integer as a FID. The ACLs, and within an ACL the UIDs, appear in no particular order. In the full list of ACLs, a given FID will appear only once. There are at most 50 top-level directory ACLs and there are at most 100 UIDs. All FIDs and UIDs are greater than 0.

The first line of input to your program is a single integer n (0 < n < 100), by itself on the line without any white space, giving the number of departments. Following that are the data for those departments.

ACLs associated with one department is a sequence of ACLs ended by "-1" by itself. Each ACL is a line of unsigned integers (1 <= x <= 2147483647) separated from each other by a single blank. The first integer on the line is the file id (FID) of the directory. The remaining numbers on the line are the user ids (UIDs) that have access. Each line will have a FID and at least one UID. There will be no duplicate UIDs on the line, but note the UIDs and FIDs are in separate spaces so a UID could be the same integer as a FID. The ACLs, and within an ACL the UIDs, appear in no particular order. In the full list of ACLs, a given FID will appear only once. There are at most 50 top-level directory ACLs and there are at most 100 UIDs. All FIDs and UIDs are greater than 0.

2
100 9 7 2 3 1 6
200 9 6 7 1 2 5 3 8
300 6 3 7 8 5
400 4 5 8
-1
100 1
200 37
-1

Case 1
3 1
3 3
2 5
Case 2
no prototypes found

1. 第一题是不是可以这样想，生了n孩子的家庭等价于n个家庭各生了一个1个孩子，这样最后男女的比例还是1:1