题解 | 小A的线段（easy version）

n, m = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(m)]

boundary = []
for i, e in enumerate(edges):
    boundary.append([e[0], 0, i])
    boundary.append([e[1], 1, i])

boundary.sort()

num = [[0, 0, 0, 0]]#边界起点，边界起点到下一个边界点的覆盖次数，边界点的出现在起始点、终止点的次数；因为边界终止点不计入覆盖次数
i = 0
for b in boundary:
    if b[1] == 0:
        if b[0] == num[i][0]:
            num[i][1] += 1
            num[i][2] += 1
        else:
            num.append([b[0], num[i][1]+1, 1, 0])
            i += 1
    else:
        if b[0] == num[i][0]:
            num[i][1] -= 1
            num[i][3] += 1
        else:
            num.append([b[0], num[i][1]-1, 0, 1])
            i += 1
# print(num)

# 回溯方法搜索所有可能的选择方式
def dfs(ind, n_r):# 此处默认输入的n_r一定是合理的
    if ind >= m:
        # print(n_r)
        return 1 #成功搜索完整个数组，没有中途中断，符合要求的一个解
    # 不删除edge[ind]
    # for i in range(1, len(n_r)-1):
    #     if n_r[i][1]<2:
    #         return 0 # 当前情况无法满足覆盖要求，后续不需要再搜索
    N = dfs(ind+1, [nu[:] for nu in n_r])
    # 删除edge[ind]
    e = edges[ind]
    for i in range(1, len(n_r)):
        if n_r[i][0]==e[0]:
            n_r[i][2] -= 1
        if n_r[i][0]==e[1]:
            n_r[i][3] -= 1
        if n_r[i][0]>=e[0] and n_r[i][0]<e[1]:#删除某条边上对计数的贡献
            n_r[i][1] -= 1
    for i in range(1, len(n_r)-1):#这里漏掉最后一个点判断，循环后补上
        if ((n_r[i][1]+n_r[i][3])<2) or (n_r[i][1]<2 and (n_r[i+1][0] - n_r[i][0])>2):
            # print(n_r)
            return N # 当前情况无法满足覆盖要求，后续不需要再搜索
    if n_r[-1][3] < 2:#补上最后一个点判断
        return N
    # print(n_r)
    N += dfs(ind+1, [nu[:] for nu in n_r])
    return N

# 判断当前的num是否满足要求
for i in range(1, len(num)-1):#这里漏掉最后一个点判断，循环后补上
    if ((num[i][1]+num[i][3])<2) or (num[i][1]<2 and (num[i+1][0] - num[i][0])>2):
        print(0)
        exit(0) # 当前情况无法满足覆盖要求，后续不需要再搜索
if num[-1][3] < 2:#补上最后一个点判断
    print(0)
    exit(0)
N = dfs(0, [nu[:] for nu in num])#二维数组num需要使用深拷贝，所以作了循环生成
# print(num)
print(N)