Dicing Game - Minimizing Maximum Wins

Dicing is a popular two‐player game in Byteotia. During a night at the dicing club, several games are organized between pairs of players. At the end of the night, the player with the highest number of wins is declared the "lucky chap". Byteasar, a most unlucky fellow, once won the title but forgot how many games he had won. Now he wonders: what is the smallest number \(k\) such that it is possible to assign winners for all games so that every player wins at most \(k\) games?

You are given the list of games played that night. In each game two players compete. Your task is to determine the minimum number \(k\) for which one can choose outcomes for all games such that no player wins more than \(k\) times and to output one valid assignment of winners.

Input Format: The first line contains a positive integer m (m ≥ 1) denoting the number of games. The following m lines each contain two strings representing the names of the two players competing in that game. (A player's name is a non‐empty string without spaces.)

Output Format: The first line should contain the minimal possible \(k\). Each of the following m lines should contain the name of the winner of the corresponding game (in the same order as the input).

Hint: One way to solve this problem is to use a flow network. Define a source connected to each game node (with capacity 1). Connect each game node to the two player nodes (each edge with capacity 1). Then, from every player node, add an edge to the sink with capacity \(k\). Using binary search on \(k\) combined with a max–flow algorithm, find the smallest \(k\) for which the maximum flow equals the total number of games.

Mathematical Formulation: Find the smallest integer \(k\) such that there exists an assignment of winners for games \(i=1,2,\dots,m\) satisfying

[ \max_{\text{player } p} ; \sum_{\text{game } i \text{ where } p \text{ wins}} 1 \le k. ]

inputFormat

Input begins with a line containing an integer m (the number of games). Each of the following m lines contains two space‑separated strings representing the names of the two players involved in that game.

outputFormat

Output the minimum possible k on the first line. Then output m lines, where the i‑th line is the name of the player who is assigned as winner of the i‑th game according to a valid assignment achieving the win constraint.

sample

3
Alice Bob
Bob Charlie
Alice Charlie

1
Alice
Bob
Charlie