多多鸡和同事们跑去大山里露营，总共有N座山，所有的山按照编号从大到小分布在一条直线上。每座山的山顶上都有多多鸡的同事。露营需要持续一个月，多多鸡负责露营物资的运送和垃圾的回收，它需要每天开车去每座山的山顶一趟，第三种是山顶间的路。每座山都有对应的第一种路和第二种路，某些山顶之间有第三种路相连。山顶间的路只有某些山顶之间有，并且只能从编号小的山开向编号大的山。
多多鸡每天都需要从山底出发，去到所有的山顶，运送物资给同事们。因为山路的特殊性，他可能要来回山底山顶多次。现在多多鸡想找出一个方案，可以保证每个山顶都去过至少一次的情况下，上山的次数尽可能少。
输入描述：
第一行是两个整数N和M，分别表示山的个数和第三种山路的数量。（3<N<200, M<N*N)
接下来M行，每行两个数Xi和Yi。表示有从Xi山顶到Yi山顶的路。
输出描述：
共一行，为最优方案的上山次数。
示例1
输入
5 4
1 3
2 3
3 4
3 5
输出
2
说明
一种方案是
第一趟从山底开始到1号山的山顶，再到3号山的山顶，再到5号山的山顶，然后下山。
第二趟从山底开始到2号山的山顶，再到3号山的山顶，再到4号山的山顶，然后下山。
示例2
输入
4 0
输出
4
说明
因为山顶之间没有路，只能上山4趟。
想用dfs搜索所有可能路径，可能不对。
# 样例1
N = 5
M = 4
edge = [[0 for i in range(N)] for j in range(N)]
edge[0][2] = 1
edge[1][2] = 1
edge[2][3] = 1
edge[2][4] = 1
# 样例2
# N = 4
# M = 0
# edge = [[0 for i in range(N)] for j in range(N)]
# 输入
# line = input()
# N = int(line.split(' ')[0])
# M = int(line.split(' ')[1])
# for i in range(N):
# line = input()
# x = int(line.split(' ')[0]) - 1
# y = int(line.split(' ')[1]) - 1
# edge[x][y] = 1
print(edge)
visited = [0] * N
print("visited:", visited)
min_path_count = N
def dfs(path_count, node_index):
global min_path_count
global visited
print("path_count=", path_count, "node_index=", node_index, "visited=", visited)
if sum(visited) >= N: # 如果所有的node都遍历了。
if path_count < min_path_count:
min_path_count = path_count
print('√')
return
if sum(edge[node_index]) == 0: # 如果node_index没有其他出边
for i in range(N):
if visited[i] == 0: # 找到一个没有遍历的节点
visited[i] += 1
print('')
dfs(path_count + 1, i) # 开始新的路径
visited[i] -= 1
else: # 如果node_index有其他出边，那么继续遍历
for i in range(N):
if edge[node_index][i] == 1:
visited[i] += 1 # 因为有的node可能被访问多次。
dfs(path_count, i) # 继续当前的路径
visited[i] -= 1 # 因为有的node可能被访问多次。
for i in range(N):
visited = [0] * N
visited[i] = 1
dfs(1, i)
print("min_path_count=", min_path_count, '\n')
