There are n chess players numbered from 0 to n - 1. You are given the results of some games.

Each result is represented by the string "u,v", meaning player u defeated player v. A smaller numerical rank represents a stronger player, and the stronger player always wins.

Use the known results and their transitive relationships to determine which players have an exact rank.

Class

ChessRankAnalyzer

Methods

countPlayersWithKnownRank

int countPlayersWithKnownRank(int n, List<String> gameResults)

Parameters

• n: The number of chess players.
• gameResults: The known game results. Each string has the format "u,v", indicating that player u defeated player v.

Returns

Return the number of players whose exact rank can be determined.

getKnownPlayerRanks

List<String> getKnownPlayerRanks(int n, List<String> gameResults)

Parameters

• n: The number of chess players.
• gameResults: The known game results in "winner,loser" format.

Returns

Return the players whose exact ranks can be determined. Each returned string must have the format "playerId,rank".

Return the strings in ascending order of playerId. Return an empty list if no player's exact rank can be determined.

Ranking Rules

• Rank 1 is the strongest rank, and rank n is the weakest rank.
• If player u defeated player v, then u has a smaller numerical rank than v.
• Results are transitive. If u defeated v and v defeated w, then u ranks above w.
• A player's rank is known only when its relative position against every other player can be determined.
• All players have distinct ranks.

Constraints

• 1 ≤ n ≤ 100
• 0 ≤ gameResults.size() ≤ n × (n - 1) / 2
• Every value in gameResults has the format "u,v".
• 0 ≤ u < n
• 0 ≤ v < n
• u != v
• Each game result appears at most once.
• The given results contain no ranking contradictions.
• No parameter value is null.

Examples

Example 1

countPlayersWithKnownRank( n = 5, gameResults = List.of("3,1", "1,4", "4,0", "0,2"))

Output: 5

The results establish the complete order 3, 1, 4, 0, 2, so every player's rank is known.

getKnownPlayerRanks( n = 5, gameResults = List.of("3,1", "1,4", "4,0", "0,2"))

Output: List.of("0,4", "1,2", "2,5", "3,1", "4,3")

Example 2

countPlayersWithKnownRank( n = 6, gameResults = List.of( "0,2", "1,2", "2,3", "2,4", "3,5", "4,5"))

Output: 2

Players 0 and 1 can appear in either order, as can players 3 and 4. However, player 2 must be third and player 5 must be sixth.

getKnownPlayerRanks( n = 6, gameResults = List.of( "0,2", "1,2", "2,3", "2,4", "3,5", "4,5"))

Output: List.of("2,3", "5,6")

Example 3

countPlayersWithKnownRank( n = 4, gameResults = List.of("0,2", "1,3"))

Output: 0

The two independent results do not establish any player's position relative to every other player.

getKnownPlayerRanks( n = 4, gameResults = List.of("0,2", "1,3"))

Output: List.of()