Limits 2s, 512 MB

You are building a new game called Dreamrise. The game is played by 2 teams and each match usually lasts around 15 minutes. You are currently building the leaderboard feature. There will be multiple leaderboards both worldwide and regional. In a leaderboard with nn teams, each team is given a unique id from 1 to nn. Every team is ranked based on its win rate within a leaderboard. If multiple teams have the same win rate, they are given the same rank. A team is unranked until they play any game.

Win rate=Number of games wonNumber of games played\text{Win rate} = \frac{\text{Number of games won}}{\text{Number of games played}}

The rank of a team=Number of teams having higher win rate+1\text{The rank of a team} = \text{Number of teams having higher win rate} + 1

You have to support 3 types of operations to implement the leaderboard feature.

  • 1 x y1\ x\ y: Teams with id xx and yy played a match. The team with id xx is the winner.

  • 2 x2\ x: Print the current rank of the team with id xx. If the team is unranked, print -1.

  • 3 z3\ z: Print the id of the team having a rank of zz. If no team is ranked zz currently, print -1. If multiple teams have the rank zz, print the team with the smallest ID.


The first line of input contains two integers nn (1n1051 ≤ n ≤ 10^5) and qq (1q51051 ≤ q ≤ 5*10^5), denoting number of teams and number of operations respectively. Next qq lines will have one of the 3 operations described in statement.

1x,y,zn1 ≤ x, y, z ≤ n.


Print the desired answer for the operation of type 2 and 3. Do not print anything for operation of type 1.


5 10
1 2 1
1 2 3
1 1 5
1 3 5
2 1
2 4
3 2
3 4
3 3
3 5

Team 2 played with Team 1, Team 3 and won both matches. Both team 1 and team 3 won with Team 5. Team 4 hasn't played any match yet.

RankTeam IDWin RateMatch Played

Large data set. Use faster I/O.

The win rate is not necessarily an integer.


Login to submit.


30% Solution Ratio
jamil314Earliest, Nov '20
nusuBotFastest, 0.5s
fsshakkhorLightest, 9.2 MB
jamil314Shortest, 2237B
Toph uses cookies. By continuing you agree to our Cookie Policy.