from typing import Optional, Union


class Player:
    """
    A player and its rating; the rating is always a positive integer (>= 0).
    """

    def __init__(self, name, rating):
        self.name = name
        assert isinstance(rating, int) and rating >= 0
        self.rating = rating

    def against(self, other: 'Player') -> 'Player':
        """
        Play a match and return the winner.
        """
        if self.rating > other.rating:
            return self
        elif self.rating == other.rating:
            # ties broken by name
            if self.name < other.name:
                return self
            else:
                return other
        else:
            return other


class TournamentTreeNode:
    """
    A tournament tree, where the leaves are players and the internal nodes are
    matches and leaves are players.
    """

    def __init__(self, left: Union['TournamentTreeNode', Player], right: Union['TournamentTreeNode', Player]):
        self.left = left
        self.right = right

    def who_won(self) -> Optional[Player]:
        """
        Return the player that won this match. If the match is not yet played (i.e. the
        left and right subtrees are not leaves), return None.
        Ties are broken by the player with the lower name (lexicographically).
        """
        if isinstance(self.left, Player) and isinstance(self.right, Player):
            return self.left.against(self.right)
        else:
            return None

    def play(self):
        """
        Play the match at this node. If the match is already played, do nothing.
        """
        if isinstance(self.left, Player) and isinstance(self.right, Player):
            return
        else:
            if isinstance(self.left, TournamentTreeNode):
                self.left.play()
                self.left = self.left.who_won()
            if isinstance(self.right, TournamentTreeNode):
                self.right.play()
                self.right = self.right.who_won()