Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A, B = [], []
for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

class Rs():
    def __init__(self):
        self.Rs = []

    def append(self, R):
        self.Rs.append(R)

    def search(self):
        count = 1
        new_nodes, count = self._search(1, count)
        while count < N:
            _new_nodes = set()
            for num in new_nodes:
                _new_node, count = self._search(num, count)
                _new_nodes.update(_new_node)
            new_nodes = _new_nodes

        return [ self.Rs[i].fastest_room for i in range(1,len(self.Rs)) ]

    def _search(self, num, count):
        r = self.Rs[num-1]
        cons = r.connection
        new_nodes = set()
        cons -= r.searched_from

        for con in cons:
            if len(self.Rs[con-1].searched_from) == 0:
                self.Rs[con-1].fastest_room = num
                self.Rs[con-1].searched_from.add(num)
                new_nodes.add(con)
                count += 1
            else:
                continue
        return new_nodes, count

class R():
    def __init__(self, num, connection):
        self.num        = num
        self.connection = connection
        self.searched_from = set([])
        self.fastest_room = None

r = Rs()
for i in range(N):
    cons = []
    for j, (a, b) in enumerate(zip(A, B)):
        if a == (i+1):
            cons.append(B[j])
        elif b == (i+1):
            cons.append(A[j])
    r.append(R(i+1, set(cons)))

l = r.search()
print("Yes")
for room in l:
    print(room)



Fixed submission:
N, M = map(int, input().split())
A, B = [], []
graph = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
    graph[a].append(b)
    graph[b].append(a)

class Rs():
    def __init__(self):
        self.Rs = []

    def append(self, R):
        self.Rs.append(R)

    def search(self):
        count = 1
        new_nodes, count = self._search(1, count)
        while count < N:
            _new_nodes = set()
            for num in new_nodes:
                _new_node, count = self._search(num, count)
                _new_nodes.update(_new_node)
            new_nodes = _new_nodes

        return [ self.Rs[i].fastest_room for i in range(1,len(self.Rs)) ]

    def _search(self, num, count):
        r = self.Rs[num-1]
        cons = r.connection
        new_nodes = set()
        cons -= r.searched_from

        for con in cons:
            if len(self.Rs[con-1].searched_from) == 0:
                self.Rs[con-1].fastest_room = num
                self.Rs[con-1].searched_from.add(num)
                new_nodes.add(con)
                count += 1
            else:
                continue
        return new_nodes, count

class R():
    def __init__(self, num, connection):
        self.num        = num
        self.connection = connection
        self.searched_from = set([])
        self.fastest_room = None

r = Rs()
for i in range(N):
    r.append(R(i+1, set(graph[i+1])))

l = r.search()
print("Yes")
for room in l:
    print(room)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A, B = [], []
for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

class Rs():
    def __init__(self):
        self.Rs = []

    def append(self, R):
        self.Rs.append(R)

    def search(self):
        count = 1
        new_nodes, count = self._search(1, count)
        while count < N:
            _new_nodes = []
            for num in new_nodes:
                _new_node, count = self._search(num, count)
                _new_nodes.extend(_new_node)
            new_nodes = _new_nodes

        return [ self.Rs[i].fastest_room for i in range(1,len(self.Rs)) ]

    def _search(self, num, count):
        r = self.Rs[num-1]
        cons = r.connection
        new_nodes = []
        cons -= r.searched_from

        for con in cons:
            if len(self.Rs[con-1].searched_from) == 0:
                self.Rs[con-1].fastest_room = num
                self.Rs[con-1].searched_from.add(num)
                new_nodes.append(con)
                count += 1
            else:
                continue
        return new_nodes, count

class R():
    def __init__(self, num, connection):
        self.num        = num
        self.connection = connection
        self.searched_from = set([])
        self.fastest_room = None

r = Rs()
for i in range(N):
    cons = []
    for j, (a, b) in enumerate(zip(A, B)):
        if a == (i+1):
            cons.append(B[j])
        elif b == (i+1):
            cons.append(A[j])
    r.append(R(i+1, set(cons)))

l = r.search()
print("Yes")
for room in l:
    print(room)



Fixed submission:
N, M = map(int, input().split())
A, B = [], []
graph = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
    graph[a].append(b)
    graph[b].append(a)

class Rs():
    def __init__(self):
        self.Rs = []

    def append(self, R):
        self.Rs.append(R)

    def search(self):
        count = 1
        new_nodes, count = self._search(1, count)
        while count < N:
            _new_nodes = set()
            for num in new_nodes:
                _new_node, count = self._search(num, count)
                _new_nodes.update(_new_node)
            new_nodes = _new_nodes

        return [ self.Rs[i].fastest_room for i in range(1,len(self.Rs)) ]

    def _search(self, num, count):
        r = self.Rs[num-1]
        cons = r.connection
        new_nodes = set()
        cons -= r.searched_from

        for con in cons:
            if len(self.Rs[con-1].searched_from) == 0:
                self.Rs[con-1].fastest_room = num
                self.Rs[con-1].searched_from.add(num)
                new_nodes.add(con)
                count += 1
            else:
                continue
        return new_nodes, count

class R():
    def __init__(self, num, connection):
        self.num        = num
        self.connection = connection
        self.searched_from = set([])
        self.fastest_room = None

r = Rs()
for i in range(N):
    r.append(R(i+1, set(graph[i+1])))

l = r.search()
print("Yes")
for room in l:
    print(room)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A, B = [], []
for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

class Rs():
    def __init__(self):
        self.Rs = []

    def append(self, R):
        self.Rs.append(R)

    def search(self):
        self.searched = [0] * len(self.Rs)

        w = 1
        count = 1
        new_nodes, count = self._search(1, w, count)
        while count < N:
            w += 1
            _new_nodes = []
            for num in new_nodes:
                _new_node, count = self._search(num, w, count)
                _new_nodes.extend(_new_node)
            new_nodes = _new_nodes

        return [ self.Rs[i].fastest_room for i in range(1,len(self.Rs)) ]

    def _search(self, num, w, count):
        r = self.Rs[num-1]
        cons = r.connection
        new_nodes = []
        cons -= r.searched_from

        for con in cons:
            weight = self.Rs[con-1].weight
            if weight is None:
                self.Rs[con-1].weight = w
                self.Rs[con-1].fastest_room = num
                self.Rs[con-1].searched_from.add(num)
                new_nodes.append(con)
                count += 1
            else:
                continue
        return new_nodes, count

class R():
    def __init__(self, num, connection):
        self.num        = num
        self.connection = connection
        self.weight     = None
        self.searched_from = set([])
        self.fastest_room = None

r = Rs()
for i in range(N):
    cons = []
    for j, (a, b) in enumerate(zip(A, B)):
        if a == (i+1):
            cons.append(B[j])
        elif b == (i+1):
            cons.append(A[j])
    r.append(R(i+1, set(cons)))

l = r.search()
print("Yes")
for room in l:
    print(room)



Fixed submission:
N, M = map(int, input().split())
A, B = [], []
graph = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
    graph[a].append(b)
    graph[b].append(a)

class Rs():
    def __init__(self):
        self.Rs = []

    def append(self, R):
        self.Rs.append(R)

    def search(self):
        count = 1
        new_nodes, count = self._search(1, count)
        while count < N:
            _new_nodes = set()
            for num in new_nodes:
                _new_node, count = self._search(num, count)
                _new_nodes.update(_new_node)
            new_nodes = _new_nodes

        return [ self.Rs[i].fastest_room for i in range(1,len(self.Rs)) ]

    def _search(self, num, count):
        r = self.Rs[num-1]
        cons = r.connection
        new_nodes = set()
        cons -= r.searched_from

        for con in cons:
            if len(self.Rs[con-1].searched_from) == 0:
                self.Rs[con-1].fastest_room = num
                self.Rs[con-1].searched_from.add(num)
                new_nodes.add(con)
                count += 1
            else:
                continue
        return new_nodes, count

class R():
    def __init__(self, num, connection):
        self.num        = num
        self.connection = connection
        self.searched_from = set([])
        self.fastest_room = None

r = Rs()
for i in range(N):
    r.append(R(i+1, set(graph[i+1])))

l = r.search()
print("Yes")
for room in l:
    print(room)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A, B = [], []
for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

class Rs():
    def __init__(self):
        self.Rs = []

    def append(self, R):
        self.Rs.append(R)

    def search(self):
        self.searched = [0] * len(self.Rs)

        w = 1
        count = 1
        new_nodes, count = self._search(1, w, count)
        #print(new_nodes, count)
        while count < N:
            w += 1
            _new_nodes = []
            for num in new_nodes:
                _new_node, count = self._search(num, w, count)
                _new_nodes.extend(_new_node)
                #print(_new_nodes, count)

            new_nodes = list(set(_new_nodes))
        return [ self.Rs[i].fastest_room for i in range(1,len(self.Rs))]

    def _search(self, num, w, count):
        r = self.Rs[num-1]
        cons = r.connection
        new_nodes = []
        for node in r.searched_from:
            cons.remove(node)
        for con in cons:
            weight = self.Rs[con-1].weight
            if weight is None:
                self.Rs[con-1].weight = w
                self.Rs[con-1].fastest_room = num
                self.Rs[con-1].searched_from.append(num)
                new_nodes.append(con)
                count += 1
            else:
                continue
        return new_nodes, count

class R():
    def __init__(self, num, connection):
        self.num        = num
        self.connection = connection
        self.weight     = None
        self.searched_from = []
        self.fastest_room = None

r = Rs()
for i in range(N):
    cons_idx = []
    for j, a in enumerate(A):
        if a == (i+1):
            cons_idx.append(j)
    cons = [ B[i] for i in cons_idx ]
    cons_idx = []
    for j, a in enumerate(B):
        if a == (i+1):
            cons_idx.append(j)
    cons.extend([ A[i] for i in cons_idx ])
    r.append(R(i+1, cons))

l = r.search()
print("Yes")
for room in l:
    print(room)



Fixed submission:
N, M = map(int, input().split())
A, B = [], []
graph = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
    graph[a].append(b)
    graph[b].append(a)

class Rs():
    def __init__(self):
        self.Rs = []

    def append(self, R):
        self.Rs.append(R)

    def search(self):
        count = 1
        new_nodes, count = self._search(1, count)
        while count < N:
            _new_nodes = set()
            for num in new_nodes:
                _new_node, count = self._search(num, count)
                _new_nodes.update(_new_node)
            new_nodes = _new_nodes

        return [ self.Rs[i].fastest_room for i in range(1,len(self.Rs)) ]

    def _search(self, num, count):
        r = self.Rs[num-1]
        cons = r.connection
        new_nodes = set()
        cons -= r.searched_from

        for con in cons:
            if len(self.Rs[con-1].searched_from) == 0:
                self.Rs[con-1].fastest_room = num
                self.Rs[con-1].searched_from.add(num)
                new_nodes.add(con)
                count += 1
            else:
                continue
        return new_nodes, count

class R():
    def __init__(self, num, connection):
        self.num        = num
        self.connection = connection
        self.searched_from = set([])
        self.fastest_room = None

r = Rs()
for i in range(N):
    r.append(R(i+1, set(graph[i+1])))

l = r.search()
print("Yes")
for room in l:
    print(room)