import bs4
import requests
from collections import deque


class Parser:
    _BAD_PREFIX_SET = {'Википедия:', 'Портал:'}

    def link_checker(self, link):
        for prefix in self._BAD_PREFIX_SET:
            if link['title'][:len(prefix)] == prefix:
                return False
        return True

    def get_links(self, html):
        soup = bs4.BeautifulSoup(html, features="html.parser")
        css_selector = 'div.mw-parser-output a[href^=\/wiki]:not([class])'
        links = soup.select(css_selector)
        return list(map(lambda link: link['title'], filter(lambda x: self.link_checker(x), links)))


class WebGraph:
    def __init__(self, start, target):
        self.start = start
        self.target = target
        self.parser = Parser()
        self.used = {start: 0}

    @staticmethod
    def build_link(link):
        return f'https://ru.wikipedia.org/wiki/{link}'

    def bfs(self):
        deq = deque()
        deq.append(self.start)
        while deq:
            link = deq.popleft()
            for other_link in self.parser.get_links(requests.get(self.build_link(link)).text):
                if other_link in self.used:
                    continue
                if other_link == self.target:
                    return self.used[link] + 1
                self.used[other_link] = self.used[link] + 1
                if self.used[other_link] > 5:
                    break
                deq.append(other_link)


graph = WebGraph('Соединённые Штаты Америки', 'Великобритания')
print(graph.bfs())