Sane's Monthly Algorithms Challenge: November 2008

Intelligent Stats (Guru Level)

You are a computer scientist for a popular online game which hosts one-on-one chess games between players across the world. After each game, the username of both players is recorded in the website's database, along with the username of the player who won.

The website has statistics for the Wins and Losses of each player. However, these statistics are poor representations since the most active members can increase their win count by 'picking' on bad players with low win-loss ratios. Some also cheat by playing against their own alternate accounts.

To help reduce this problem, they want to add an intelligent stat to each user, which indicates how many players the user “can” beat, given the playing history of all players and the following logical rule:

    Player A can beat Player B if and only if Player A and Player B have different usernames and:
            Player A has beat Player B
            or
            Player A has beat Player C and Player C can beat Player B.

This statistic will hopefully provide an incentive for users to compete against better players, and to not repeatedly pick on the same person.

Your job is, given the database of playing history, generate the database containing this new statistical attribute for each player.

Input

The first line contains an integer n (1 ≤ n ≤ 10,000).

The next n lines each contain two alphanumeric names of lengths no longer than 20, separated by a space. This line indicates that the first user “has” beat the second user. Names are case sensitive. A player can never play against himself.

Output

On the first line, output an integer k (2 ≤ k ≤ 20,000), representing the number of distinct names mentioned in the input file.

For each of the next k lines to follow, output a name you have not yet mentioned in the output file, followed by the number of users he/she “can” beat (the order of the output file does not matter).

Sample Input

7
Jim Denise
Noobie111 AwesumChessPlyr1337
Gerald AwesumChessPlyr1337
AwesumChessPlyr1337 Denise
Denise 2GudAtChessLOL
2GudAtChessLOL AwesumChessPlyr1337
Jim Gerald

Sample Output

6
Jim 4
Gerald 3
Noobie111 3
Denise 2
2GudAtChessLOL 2
AwesumChessPlyr1337 2

Diagram

All Submissions
Best Solutions

Point Value: 10 (partial)
Time Limit: 6.00s
Memory Limit: 128M
Added: Jan 15, 2009
Author: DrSane

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)