Сталкер (не проходит по памяти)

def solution():
    def dfs(vert):
        neighbour_vert = graf[vert]
        graf[vert] = False
        for now_vert in neighbour_vert:
            if graf[now_vert] != False:
                dfs(now_vert)
        if len(intersection_con[vert]) >= 1:
            for con_two in intersection_con[vert]:
                graf_con[con_two].append(count_con)
                graf_con[count_con].append(con_two)
        intersection_con[vert].append(count_con)
 
    houses, maps = map(int, input().split())
    intersection_con = [[] for _ in range(houses+1)]    # для каждого дома записываем с какими связностями он пересекается
    count_con = 0
    graf_con = []   # граф связностей
    for _ in range(maps):
        # roads = int(data[i])
        roads = int(input())
        graf = {}
        for _ in range(roads):
            # house_one, house_two = map(int, data[i].split())
            house_one, house_two = map(int, input().split())
            try:
                graf[house_one].append(house_two)
            except KeyError:
                graf[house_one] = [house_two]
            try:
                graf[house_two].append(house_one)
            except KeyError:
                graf[house_two] = [house_one]
        for vert in graf:
            if graf[vert] != False:
                graf_con.append([])
                dfs(vert)   # проверяем связность
                count_con += 1
 
    graf_con = [set(intersection) for intersection in graf_con]     # чтобы ребра не повторялись
    start_cons = intersection_con[1]
    end_cons = intersection_con[houses]
    intersection_con = []
    queue = [start_con for start_con in start_cons]
    distance = [-1]*(count_con)
    for st_con in queue:
        distance[st_con] = 1    # за первую загруженную карту надо заплатить
 
    for con in queue:
        for neighbour_con in graf_con[con]:
            if distance[neighbour_con] == -1:
                distance[neighbour_con] = distance[con] + 1
                queue.append(neighbour_con)
 
    ans = -1   # минимум переключений карт
    for end_con in end_cons:
        if (distance[end_con] < ans and distance[end_con] != -1) or ans == -1:
            ans = distance[end_con]
    print(ans)
solution()

import math
 
def solution_new():
    from collections import deque
 
    n, k = map(int, input().split())
    graph = {}
    maps = {i: set() for i in range(1, n + 1)}
    start_maps = set()
    end_maps = set()
    for i in range(1, k + 1):
        for _ in range(int(input())):
            x, y = map(int, input().split())
            maps[i].add(x)
            maps[i].add(y)
            key1, key2 = (i, x), (i, y)
            graph.setdefault(key1, set()).add(key2)
            graph.setdefault(key2, set()).add(key1)
            if x == 1 or y == 1:
                start_maps.add(i)
            if x == n or y == n:
                end_maps.add(i)
 
 
    # print(graph, sep='\n')
    # print(maps)
    count_cost = 1
    queue = [(map, 1) for map in start_maps]
    # print(queue)
    queue_2 = []
    viseted = {map_house:False for map_house in graph.keys()}
 
    # print(viseted)
    while len(queue) != 0:
        for map_house in queue:
            viseted[map_house] = count_cost
            for neighbour_map_house in graph[map_house]:
                if viseted[neighbour_map_house] == False:
                    viseted[neighbour_map_house] = count_cost
                    queue_2.append(neighbour_map_house)
 
            # graph[map_house] = count_cost
        count_cost += 1
        queue = []
 
        for map_house in queue_2:
            for num_map in range(1, k+1):
                try:
                    if viseted[(num_map, map_house[1])] == False:
                        queue.append((num_map, map_house[1]))
                except KeyError:
                    pass
 
    ans = math.inf
    for num_map in end_maps:
        if viseted[(num_map, n)] != False and viseted[(num_map, n)] < ans:
            ans = viseted[(num_map, n)]
 
    if ans == math.inf:
        print(-1)
    else:
        print(ans)
 
solution_new()

# coding: utf-8
# 40м - paperCode; 100 + 88 + 20 - Python; 100 min + 26 + 55 + 77 - C++; 100 +
import math
 
def solution_new():
    from collections import deque
 
    n, k = map(int, input().split())
    graph = {}
    maps_for_house = {i:set() for i in range(1, n+1)} # для каждого здания запоминаем карты, на который оно расположено
    start_maps = set()
    end_maps = set()
    for i in range(1, k + 1):
        for _ in range(int(input())):
            x, y = map(int, input().split())
            maps_for_house[x].add(i)
            maps_for_house[y].add(i)
            key1, key2 = (i, x), (i, y)
            graph.setdefault(key1, set()).add(key2)
            graph.setdefault(key2, set()).add(key1)
            if x == 1 or y == 1:
                start_maps.add(i)
            if x == n or y == n:
                end_maps.add(i)
 
    count_cost = 0
    queue = deque()
    for num_map in start_maps:
        queue.append((num_map, 1))
 
    viseted = {map_house:False for map_house in graph.keys()}
    while len(queue) != 0:
        count_cost += 1
        queue_2 = deque()
        while len(queue) != 0:
            map_house = queue.pop()
            viseted[map_house] = count_cost
            for neighbour_map_house in graph[map_house]:
                if viseted[neighbour_map_house] == False:
                    viseted[neighbour_map_house] = count_cost
                    queue.append(neighbour_map_house)
                    queue_2.append(neighbour_map_house)
 
        queue = deque()
        while len(queue_2) != 0:
            map_house = queue_2.pop()
            for num_map in maps_for_house[map_house[1]]:
                try:
                    if viseted[(num_map, map_house[1])] == False:
                        queue.append((num_map, map_house[1]))
                except KeyError:
                    pass
 
    ans = math.inf
    for num_map in end_maps:
        if viseted[(num_map, n)] != False and viseted[(num_map, n)] < ans:
            ans = viseted[(num_map, n)]
 
    if ans == math.inf:
        print(-1)
    else:
        print(ans)
 
solution_new()