from typing import List
from typing import Optional


def get_shift_of_one_to_one_match(matches: List[List[bool]]) -> Optional[int]:
    """
    Matches is an n x n matrix representing a directed bipartite graph.
    Item i is connected to item j if matches[i][j] = True
    We try to find a shift k such that each item i is matched to an item j + shift

    usecase:
     for other_relations a shift 'shift' of the greenyellow intervals must exist such that other_relation is satisfied
     for each pair {(id_from, index), (id_to, index + shift)} of greenyellow intervals of signal groups id_from and
     id_to.
    :param matches: n x n matrix
    :return: shift or None if no such shift can be found
    :raises ValueError when matches is not an nxn boolean matrix
    """
    value_error_message = "matches should be an nxn boolean matrix"
    n = len(matches)
    if not isinstance(matches, list):
        raise ValueError(value_error_message)
    for row in matches:
        if not isinstance(matches, list) or len(row) != n:
            raise ValueError(value_error_message)
        if not all(isinstance(item, bool) for item in row):
            raise ValueError(value_error_message)

    for shift in range(n):
        # example:
        #  suppose matches equals:
        #      [[False, True, False], [False, False, True],[True, False, False]]
        #  then a shift of 1 to the left would give
        #      np.array([[True, False, False], [False, True, False],[False, False, True]])
        #  this has all diagonal elements
        #  below we do this check more efficiently for a shift of 'shift' to the left.
        if all(matches[row][(row + shift) % n] for row in range(n)):
            return shift
    return None