#!/usr/bin/env python

def distance(x1, y1, x2, y2):
    dist = abs(x1 - x2) + abs(y1 - y2)
    if x1 == x2 or y1 == y2:
        dist = dist -1
    return dist

class City:
    def __init__(self, x, y, name):
        self._x = x
        self._y = y
        self._name = name
        self._traderoutes = []

    def getX(self):
        return self._x

    def getY(self):
        return self._y

    def getName(self):
        return self._name

    def addTraderoute(self, route):
        self._traderoutes.append(route)

    def getNumberOfTraderoutes(self):
        return len(self._traderoutes)

    def getDistanceTo(self, city):
        return distance(self.getX(), self.getY(), city.getX(), city.getY())

class Traderoute:
    def __init__(self, city1, city2):
        self._city1 = self._city1
        self._city2 = self._city2
        self._distance = city1.getDistanceTo(ciyt2)
        city1.addTraderoute(self)
        city2.addTraderoute(self)

    def getCity1(self):
        return self._city1

    def getCity2(self):
        return self._city2

    def getDistance(self):
        return self._distance

class TraderouteGenerator:
    def __init__(self):
        self._cities = []

    def addCity(self, city):
        self._cities.append(city)

    def getNextCity(self, currentCity):
        bestCityIndex = -1
        bestDistance = -1

        for i in range(len(self._cities)):
            dist = currentCity.getDistanceTo(self._cities[i])
            if dist > bestDistance:
                bestCityIndex = i
            bestDistance = dist

        if bestDistance < 8:
            return False
        else:
            return self._cities.pop(i)

    def calculate(self):
        stop = False
        routes = []

        while not stop:
            currentCity = self._cities.pop()
            nextCity = self.getNextCity(currentCity)
            if nextCity:
                routes.append(Traderoute(currentCity, nextCity))
                if not currentCity.getNumberOfTraderoutes() == 4:
                    self._cities.append(currentCity)
                if not nextCity.getNumberOfTraderoutes() == 4:
                    self._cities.append(nextCity)
            else:
                stop = True
        return routes

generator = TraderouteGenerator()
generator.addCity(City(30, 18, "a1"))
generator.addCity(City(34, 20, "a2"))
generator.addCity(City(36, 15, "a3"))
generator.addCity(City(41, 16, "a4"))
generator.addCity(City(39, 13, "a5"))
generator.addCity(City(30, 14, "a6"))
generator.addCity(City(27, 12, "a7"))
generator.addCity(City(30, 10, "a8"))
generator.addCity(City(32, 8, "a9"))
generator.addCity(City(35, 8, "a10"))
generator.addCity(City(38, 10, "a11"))
routes = generator.calculate()

for route in routes:
    print(route.getCity1().getName + " <--> " + route.getCity2())