多多雞和同事們跑去大山里露營乱凿，總共有N座山倍试，所有的山按照編號從大到小分布在一條直線上。每座山的山頂上都有多多雞的同事亡嫌。露營需要持續(xù)一個月，多多雞負(fù)責(zé)露營物資的運送和垃圾的回收掘而，它需要每天開車去每座山的山頂一趟挟冠，第三種是山頂間的路。每座山都有對應(yīng)的第一種路和第二種路袍睡，某些山頂之間有第三種路相連知染。山頂間的路只有某些山頂之間有，并且只能從編號小的山開向編號大的山斑胜。
多多雞每天都需要從山底出發(fā)控淡，去到所有的山頂，運送物資給同事們止潘。因為山路的特殊性掺炭，他可能要來回山底山頂多次。現(xiàn)在多多雞想找出一個方案凭戴，可以保證每個山頂都去過至少一次的情況下涧狮，上山的次數(shù)盡可能少。
輸入描述：
第一行是兩個整數(shù)N和M，分別表示山的個數(shù)和第三種山路的數(shù)量者冤。（3<N<200, M<N*N)
接下來M行吧享，每行兩個數(shù)Xi和Yi。表示有從Xi山頂?shù)結(jié)i山頂?shù)穆贰?/p>
輸出描述：
共一行譬嚣，為最優(yōu)方案的上山次數(shù)钢颂。
示例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: # 找到一個沒有遍歷的節(jié)點
visited[i] += 1
print('')
dfs(path_count + 1, i) # 開始新的路徑
visited[i] -= 1
else: # 如果node_index有其他出邊秩冈，那么繼續(xù)遍歷
for i in range(N):
if edge[node_index][i] == 1:
visited[i] += 1 # 因為有的node可能被訪問多次本缠。
dfs(path_count, i) # 繼續(xù)當(dāng)前的路徑
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')
