I tried a variant of BFS where instead of creating the edges of the complement, each time I search the pe (primary edges) and take for j in notdiscovered where (i,j) != pe and (j,i) != pe. notdiscovered starts with all vertices. Instead of adding to discovered, I discard from notdiscovered. I found it was essential to do while q and notdiscovered. notdiscovered becomes empty very fast, and then everything is found already. Without that, it times out.

Editorial is very bad. It doesn't explain clearly the essesntial concepts.

1. How to convert the graph to a complement graph efficiently? I was trying to put all the edges first in N2 approach. Like for node 1 put 2,3,4... , for node 2 put 1,3,4.... and so on. and then deleting the edges which was given as input. How not to do this is still not clear from the editorial.

2. What is the relationship between L1 and L2? Was djikstra or any other single source path algorithm was used?

It will be great if some more effort can be put on the editorials as they are the source of learning.

Here's my Python 3 solution. Hope it helps someone.

tests = int(input())

for _ in range(tests):
    [n, e] = [int(i) for i in input().split(" ")]
    dists = [1] * n
    roads = {}
    for _ in range(e):
        [n1, n2] = [int(i) for i in input().split(" ")]
        if n1 not in roads:
            roads[n1] = set()
        if n2 not in roads:
            roads[n2] = set()
        roads[n1].add(n2)
        roads[n2].add(n1)
    start_loc = int(input())
    not_visited = roads[start_loc] if start_loc in roads else set()
    newly_visited = set()
    curr_dist = 2
    while len(not_visited) > 0:
        for i in not_visited:
            diff = not_visited | roads[i]
            if len(diff) < n:
                dists[i-1] = curr_dist
                newly_visited.add(i)
        not_visited = not_visited - newly_visited
        newly_visited = set()
        curr_dist += 1
    del dists[start_loc-1]
    print(" ".join(str(i) for i in dists))

Will not give a solution but this can be solved without the complement graph. Check on google how to do BFS on complementary graph :)

Just bought test set #7. It's 35,5MB of data. Difficult to even find editor that is able open that. I also modified code to just read input. It took 3,5 sec just to read input for Scala (readLine split toInt). Last test set is a joke!