← 返回 google 的题目列表Determine Players with Uniquely Identifiable Ranks
类型:online_judge
There are n chess players numbered from 0 to n - 1. You are given partial match results gameResults, where each pair (u, v) means that player u defeated player v.
All players are known to have a strict total ranking: a smaller rank means a stronger player, and every higher-ranked player always defeats every lower-ranked player. gameResults provides only some results, but is guaranteed to be consistent with at least one total ranking.
Results may be inferred transitively: if a beat b and b beat c, then a is known to rank above c.
For each player, determine whether their rank is uniquely determined across all total rankings consistent with the known results. Output every player whose rank is uniquely determined, together with that rank, ordered by player ID.
The rank of player x is defined as one plus the number of distinct players known, after transitive inference, to defeat x.
Input Format
First line: two integers n m, the number of players and results.
Next m lines: two integers u v, meaning u defeated v.
Output Format
First print k, the number of players with uniquely determined ranks.
Then print k lines, each containing player rank.
Constraints
1 <= n <= 500
0 <= m <= n * (n - 1) / 2
0 <= u, v < n, u != v
The input contains no cycle and is consistent with a strict total ranking.
Example
Input
4 3
0 1
1 2
2 3
Output
4
0 1
1 2
2 3
3 4