AtCoder Beginner Contest 209 D - Collision【Python】

https://atcoder.jp/contests/abc209/tasks/abc209_d

AtCoder ProblemsのRecommendationでDifficulty: 686、Solve Probability: 37%でした。
幅優先探索で街0から各街への距離を求め、その値がクエリの2つの街それぞれ偶数同士か奇数同士の場合はTown、それ以外の場合はRoadになる事に気づいたためとくことができました。

from collections import deque
N, Q = map(int, input().split())

G = []
for _ in range(N):
    G.append([])

for i in range(N-1):
    a, b= map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

dist = [-1] * N

que = deque()
que.append(0)
dist[0] = 0

while len(que) > 0:
    i = que.popleft()
    for i2 in G[i]:
        if dist[i2] == -1:
            dist[i2] = dist[i] + 1
            que.append(i2)

for i in range(Q):
    c, d = map(int, input().split())
    if (dist[c-1] % 2 == 0 and dist[d-1] % 2 == 0) or (dist[c-1] % 2 != 0 and dist[d-1] % 2 != 0):
        print('Town')
    else:
        print('Road')