Удаление ребра в графе и поиск пути

У меня есть неориентированный граф состоящий из n вершин и n ребёр. Мне нужно быстро отвечать на запрос, существует ли путь из точки А в точку В, если я удалю определённое ребро из точки А.

Сначала я написал простенький DFS, который запускается из точки А и ищет путь в точку В. Но когда мне нужно было искать путь из нескольких точек в точку В (при том что у каждой точки я удаляю ребро и пытаюсь найти путь), я понял, что это работает слишком долго.

У меня уже есть некоторые представления об этом графе, например, я знаю, что это дерево с одним дополнительным ребром. Правда мне это никак не помогает и у меня совершенно нет идей как быстро искать существование пути.

Можете дать подсказки? Хотя бы тему, которую стоит лучше изучить.