How to add 'Circle' size legend to Folium map (in python) and how to annotate text so it's visible in all cases?

Question

Below find my piece of code. I have a map of Europe and some cities I want to mark and their population size. I want to mark those cities with 'Circle' and the size should correspond to the scaled 'Population'.

1. I am trying to add the legend of 'Circle' size to this map, but I couldn't find a way to do it. With Circle Layer there is no option to add the legend.

2. I am also trying to annotate the City names on the map using DivIcon, and it does work, but some cities are too close to each other, so I would prefer if I can move the names of those cities further away from the corresponding dot and connect them with a line.

Just to mention, here I show only some UK cities, but in general I have a map of entire Europe and a lot of cities, so those city names in the UK are really not visible.

Does anyone have an idea on how to do this? Support for Folium on the web is not so extensive, so I couldn't find anything similar.

import pandas as pd
import numpy as np
import folium
import json
import geopandas as gpd
# Pretty display for notebooks
%matplotlib inline

data = [['Birmingham', 1141374, 52.4796992, -1.9026911],
          ['Bradford', 537173, 53.7944229, -1.7519186],
          ['Bristol', 463405, 51.4538022, -2.5972985],
          ['Edinburgh', 518500, 55.9533456, -3.1883749],
          ['Glasgow', 626410, 55.8609825, -4.2488787],
          ['Leeds', 789194, 53.7974185, -1.5437941],
          ['Liverpool', 494814, 53.407154, -2.991665]]
cities = pd.DataFrame(data, columns = ['City', 'Population', 'Latitude', 'Longitude'])

europe = #geojson file of Europe dowloaded from https://ec.europa.eu/eurostat/web/gisco/geodata/reference-data/administrative-units-statistical-units/countries

import folium.plugins
from folium.features import *

# adding the DivIcon element for the text annotation
class DivIcon(MacroElement):
    def __init__(self, html='', size=(30,30), anchor=(0,0), style=''):
        """TODO : docstring here"""
        super(DivIcon, self).__init__()
        self._name = 'DivIcon'
        self.size = size
        self.anchor = anchor
        self.html = html
        self.style = style

        self._template = Template(u"""
            {% macro header(this, kwargs) %}
              <style>
                .{{this.get_name()}} {
                    {{this.style}}
                    }
              </style>
            {% endmacro %}
            {% macro script(this, kwargs) %}
                var {{this.get_name()}} = L.divIcon({
                    className: '{{this.get_name()}}',
                    iconSize: [{{ this.size[0] }},{{ this.size[1] }}],
                    iconAnchor: [{{ this.anchor[0] }},{{ this.anchor[1] }}],
                    html : "{{this.html}}",
                    });
                {{this._parent.get_name()}}.setIcon({{this.get_name()}});
            {% endmacro %}
            """)

# creating the map
map = folium.Map(location=[53.7974185, -1.5437941], zoom_start=4, tiles=None)
style1 = {'fillColor': '#4682b4', 'fill': True, 'weight': 1, 'opacity': 0.3, 'fillOpacity': 1}
style2 = {'color': 'black', 'weight': -1, 'opacity': 0.2}

folium.GeoJson(
    europe,
    name='Europe',
    overlay=False,
    control= False,
    style_function = lambda x: style2).add_to(map)
        
# Adding a circle for each selected city
for idx, city in cities.iterrows():
    folium.Circle(location=(city['Latitude'], city['Longitude']),
                  popup=city['City'],
                  radius=city['Population']/10000,
                  fillColor= 'red',
                  color= 'red', 
                  fill= True,
                  fillOpacity= 0,
                  opacity= 1,
                  weight= 2
                 ).add_to(map)
    folium.Marker(location=(city['Latitude'], city['Longitude']),
                  icon=DivIcon(
                     size=(75,25),
                     anchor=(50,-3),
                     html=city.City,
                     style='font-size:13px; color:black; text-align: center')).add_to(map)

map