import sys
sys.setrecursionlimit(2000)

def solve():
    print("Input: ")
    adj = {
        "A1": ["J1", "J2"],
        "A2": ["J1"],
        "A3": ["J2", "J3"]
    }
    print(adj)
    
    
    left_nodes = ["A1", "A2", "A3"]
    match = {}
    visited = set()

    def dfs(u):
        for v in adj.get(u, []):
            if v in visited:
                continue
            visited.add(v)
            
            if v not in match or dfs(match[v]):
                match[v] = u
                return True
        return False

    matches_count = 0
    for u in left_nodes:
        visited.clear()
        if dfs(u):
            matches_count += 1

    print(f"Maximum Matching Size = {matches_count}")
    print("Matching:")
    
    result_pairs = [(u, v) for v, u in match.items()]
    result_pairs.sort()
    
    for applicant, job in result_pairs:
        print(f"{applicant} - {job}")

if __name__ == "__main__":
    solve()