def parse_data(input_str: str) -> tuple:
    """
    解析输入数据
    Args:
        input_str (str):输入的字符串

    Returns: tuple
        行星个数 int
        行星可以连接的所有组合 list
        要摧毁的所有行星 list
    """
    union_list = []
    destroy_list = []

    input_str_list = input_str.split('\n')
    planet_num, union_num, destroy_num = 0, 0, 0

    for line in input_str_list:
        line = line.strip()
        if not line:
            continue
        line_list = line.split(' ')
        if len(line_list) > 1:
            if not planet_num and not union_num:
                planet_num, union_num = int(line_list[0]), int(line_list[1])
            else:
                union_list.append((int(line_list[0]), int(line_list[1])))
        else:
            if not destroy_num:
                destroy_num = int(line_list[0])
            else:
                destroy_list.append(int(line_list[0]))
    return planet_num, union_list, destroy_list