Optimize Breadth First Search

Question

I have been getting timeout errors for this particular graph theory problem. I tried optimizing my code as much as I could but it's still not meeting the HackerRank performance standards for this problem. To give you a basic run down, I first assume a fully connected graph and run a BFS on it, avoiding the edges which are city roads. But instead of creating the actual graph for every test case, I made a generator which lets my BFS function iterate through only the nodes to which the current node is connected by a village edge. Any hint on how I can optimize it more would be appreciated.

from collections import deque
T = input()

# BFS
def return_nodes(N,a,edges):
    for i in xrange(1,N+1):
        if i != a and (i,a) not in edges and (a,i) not in edges:
            yield i

def bfs(start,N,edges):
    S,q,dist = set(),deque(),{}
    S.add(start)
    q.append(start)
    dist[start] = 0
    while q:
        current_node = q.popleft()
        for i in return_nodes(N,current_node,edges):
            if i in S: continue
            S.add(i)
            q.append(i)
            dist[i] = dist[current_node] + 1
    return dist

for i in xrange(T):
    N,M = map(int,raw_input().split())
    # Main roads/edges
    main_edges = set()
    for j in xrange(M):
        a,b = map(int,raw_input().split())
        main_edges.add((a,b))
    start = input()
    dist = bfs(start,N,main_edges)
    for k in dist:
        if k != start:
            print dist[k],
    print " "