Submission #3785656

---

Source Code Expand

N = int(input())
A, B = map(int, input().split(" "))
M = int(input())
XY = [list(map(int, input().split(" "))) for _ in range(M)]

routes = [set() for _ in range((N+1))]
for x, y in XY:
    routes[x].add(y)
    routes[y].add(x)

visited = set()
# visited.add(A)
p = [0]*(N+1)
p[A] = 1

now_q = {A}
while now_q:
    next_q = set()
    for this_n in now_q:
        visited.add(this_n)

        for n in routes[this_n]-visited:
            p[n] = (p[n]+p[this_n]) % (10**9+7)
            next_q.add(n)
    if B in next_q:
        break
    now_q = next_q

print(p[B])

Submission Info

Judge Result