2007/2008 SOUTHERN CALIFORNIA REGIONAL
ACM INTERNATIONAL COLLEGIATE PROGRAMMING CONTEST

Problem 1
Role Prototypes

HotSwampBuggies.com has just completed its outside audit for this year. One item cited is the lack of business rules for assigning permissions to the company's shared file server. Permissions have not been assigned completely randomly; typically, they have been assigned by copying existing permissions (e.g., "I need an account `just like Joe's'").
The analysts are working to identify roles for all employees, and the permissions each role should have. Your team is to provide information about the currently assigned permissions to the analysts.
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 that will split the users into equivalence classes where all members of a class have access to exactly the same directories.
Input to your program will be a sequence of ACLs terminated by end-of-file. Each ACL is a line of unsigned integers between 1 and 2,147,483,647 inclusive, separated from each other by single spaces. 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 an FID and at least one UID. There will be no duplicate UIDs on the line; but note the UIDs and FIDs are in separate numbering spaces, so a UID could have the same value as an FID. The ACLs, and the UIDs within an ACL, appear in no particular order. In the full list of ACLs, a given FID will appear only once.
There are at most 50 ACLs and there are at most 100 UIDs.
For every class with at least two members, your program is to print a line with the number of members in the class, a single space, and the smallest UID in the class. The printed line is not to contain any leading or trailing whitespace. All values are to be printed without signs or leading zeroes. Sort the output by the number of members, descending, and then by the UIDs, ascending.
If there are no such classes, print a line containing the message "no prototypes found" beginning in the first column.


Sample Input

 93887874 207756430 204131096 57958257 122956127 19806711 29278520
 53654434 207756430 204131096 57958257 122956127 19806711 29278520 204581770 106327401
 115951964 122956127 19806711 29278520 204581770 106327401
 116165615 71582695


Output for the Sample Input

 3 19806711
 3 57958257
 2 106327401



File translated from TEX by TTH, version 3.77.
On 17 Nov 2007, 19:17.