def count_match_pairings(n):
    """
    Đệ quy: Đếm số cách ghép cặp n đội thành các trận đấu.

    Với n đội (n chẵn), số cách ghép cặp thành n/2 trận đấu là:
        f(0) = 1  (không có đội nào → 1 cách: không làm gì)
        f(2) = 1  (2 đội → 1 trận)
        f(n) = (n - 1) * f(n - 2)

    Giải thích: Đội thứ nhất có (n-1) lựa chọn đối thủ,
    sau khi ghép xong thì còn (n-2) đội → gọi đệ quy f(n-2).

    Args:
        n: Số đội (phải là số chẵn không âm).

    Returns:
        Số cách ghép cặp các đội thành trận đấu.

    Raises:
        ValueError: Nếu n là số lẻ hoặc âm.
    """
    if n < 0 or n % 2 != 0:
        raise ValueError("Số đội phải là số chẵn không âm")

    # Base case
    if n == 0 or n == 2:
        return 1

    # Đệ quy: đội đầu tiên chọn 1 trong (n-1) đối thủ,
    # còn lại (n-2) đội tiếp tục ghép cặp
    return (n - 1) * count_match_pairings(n - 2)


def display_match_bracket_recursive(teams, match_list=None, depth=0):
    """
    Đệ quy: Hiển thị một ví dụ cách ghép cặp trận đấu.

    Hàm đệ quy lấy 2 đội đầu tiên ghép thành 1 trận,
    rồi gọi đệ quy với các đội còn lại.

    Args:
        teams: Danh sách các đội còn lại cần ghép.
        match_list: Danh sách tích lũy các trận đã ghép.
        depth: Độ sâu đệ quy (dùng để đánh số trận).
    """
    if match_list is None:
        match_list = []

    # Base case: không còn đội nào để ghép
    if len(teams) < 2:
        return match_list

    # Bước đệ quy: ghép 2 đội đầu tiên, gọi lại với phần còn lại
    match_num = depth + 1
    match_list.append((match_num, teams[0], teams[1]))
    return display_match_bracket_recursive(teams[2:], match_list, depth + 1)


def print_bracket(n):
    """
    In kết quả ghép cặp cho n đội bằng đệ quy.

    Args:
        n: Số đội (phải là số chẵn không âm).
    """
    if n < 2:
        print("Cần ít nhất 2 đội để tạo trận đấu.")
        return

    teams = list(range(1, n + 1))
    matches = display_match_bracket_recursive(teams)

    print(f"\n--- Ví dụ ghép cặp cho {n} đội (Đệ quy) ---")
    for match_num, team_a, team_b in matches:
        print(f"  Trận {match_num}: Đội {team_a} vs Đội {team_b}")


if __name__ == "__main__":
    # Tính số cách ghép cặp cho các số đội khác nhau
    print("=" * 50)
    print("  BÀI TOÁN GHÉP CẶP TRẬN ĐẤU (ĐỆ QUY)")
    print("=" * 50)

    for num_teams in range(2, 12, 2):
        ways = count_match_pairings(num_teams)
        print(f"  {num_teams} đội → {ways} cách ghép cặp")

    print("-" * 50)

    # Ví dụ chi tiết với 6 đội
    n = 6
    total = count_match_pairings(n)
    print(f"\nVới {n} đội, tổng có {total} cách ghép cặp trận đấu.")
    print_bracket(n)

    # Ví dụ chi tiết với 8 đội (giải đấu lớn hơn)
    n = 8
    total = count_match_pairings(n)
    print(f"\nVới {n} đội, tổng có {total} cách ghép cặp trận đấu.")
    print_bracket(n)