atcoder abc213dに関する質問

前提・実現したいこと

atcoderの問題でエラーが出たのですが、どうしたらいいのかわからないのでご教授お願い致します。問題のurl https://atcoder.jp/contests/abc213/tasks/abc213_d

発生している問題・エラーメッセージ

Traceback (most recent call last):
  File "./Main.py", line 36, in <module>
    dfs(1)
  File "./Main.py", line 32, in dfs
    dfs(j)
  File "./Main.py", line 32, in dfs
    dfs(j)
  File "./Main.py", line 35, in dfs
    dfs(j)
  File "./Main.py", line 26, in dfs
    visited[p] = True
TypeError: list indices must be integers or slices, not NoneType

該当のソースコード

python
1import sys
2input = sys.stdin.readline
3sys.setrecursionlimit(100000000)
4ans = []
5n = int(input())
6graph = []
7for i in range(n+1):
8  graph.append([])
9for i in range(n-1):
10  a, b = map(int, input().split())
11  graph[a].append(b)
12  graph[b].append(a)
13
14for i in range(n+1):
15  graph[i].sort()
16  
17visited = []
18for i in range(n+1):
19  visited.append(False)
20first = []
21for i in range(n+1):
22  first.append(None)
23
24def dfs(p):
25  ans.append(p)
26  visited[p] = True
27  ok = 0
28  for j in graph[p]:
29    if not visited[j]:
30      first[p] = j
31      ok = 1 
32      dfs(j)
33  if ok == 0 and p != 0:
34    j = first[p]
35    dfs(j)
36dfs(1)
37print(*ans)

試したこと

TypeErrorなので型（文字列、数字、リストや辞書）の種類が違うということなんでしょうけど、どこのコードをどう変えたらいいかわかりませんでした。初心者質問ですいません。

補足情報（FW/ツールのバージョンなど）

#解説のコード

python
1import sys
2sys.setrecursionlimit(300000)
3
4N=int(input())
5G=[[] for i in range(N+1)]
6for i in range(N-1):
7  a,b=map(int,input().split())
8  G[a].append(b)
9  G[b].append(a)
10
11for i in range(N+1):G[i].sort()
12
13ans=[]
14def dfs(crr,pre):
15  ans.append(crr)
16  for nxt in G[crr]:
17    if nxt!=pre:
18      dfs(nxt,crr)
19      ans.append(crr)
20
21dfs(1,-1)
22print(*ans)