Compile Participant Results

This problem requires you to compile a list of participants who have solved at least one problem and then sort the results. The participants must be sorted by the number of unique problems solved (in descending order). If two or more participants have solved the same number of problems, they should be sorted lexicographically by their user IDs.

The sorting criteria can be expressed by the following formula: if participant A solved $$P_A$$ problems and participant B solved $$P_B$$ problems, then A comes before B if $$P_A > P_B$$, or if $$P_A = P_B$$ and A's user ID is lexicographically smaller than B's.

inputFormat

The first line of input contains two space-separated integers, $$n$$ and $$m$$, where $$n$$ is the number of participants and $$m$$ is the number of submissions.

The next $$m$$ lines each contain a submission record. Each record consists of a string (the participant's user ID) and an integer (the problem ID), separated by a space.

outputFormat

For each participant who has solved at least one problem, output their user ID and the number of unique problems they have solved, separated by a space. The output should be sorted by the number of problems solved in descending order; if there is a tie, sort lexicographically by user ID. Each participant's result should be printed on a new line.

5 6
alice 1
bob 2
alice 2
charlie 1
alice 3
bob 1

alice 3
bob 2
charlie 1