Unmet Dependencies – containerd Breaks docker.io

I have a Ubuntu 18.04.6 LTS machine that cannot be updated due to a dependency error, which I don't know how to solve.

It started after I did do-release-upgrade from 16.04.7.

1. apt update works fine, then apt upgrade gives this error:

You might want to run 'apt --fix-broken install' to correct these.
The following packages have unmet dependencies:
    containerd : Breaks: docker.io (< 19.03.13-0ubuntu4) but 18.09.7-0ubuntu16.04.7 is installed
E: Unmet dependencies. Try 'apt --fix-broken install' with no packages (or specify a solution).

2. I try apt --fix-broken install, as suggested, but it gives yet another error, and this time, a very unespecific one:

dpkg: error processing archive /var/cache/apt/archives/docker.io_20.10.12-0ubuntu2~18.04.1_amd64.deb (--unpack):
Error were encountered while processing:
    /var/cache/apt/archives/docker.io_20.10.12-0ubuntu2~18.04.1_amd64.deb
E: Sub-process /usr/bin/dpkg/ returned an error code (1)

3. As it suggest me to run apt autoremove, I try that command instead, which leads me to the first error again:

You might want to run 'apt --fix-broken install' to correct these.
The following packages have unmet dependencies:
    containerd : Breaks: docker.io (< 19.03.13-0ubuntu4) but 18.09.7-0ubuntu16.04.7 is installed
E: Unmet dependencies. Try 'apt --fix-broken install' with no packages (or specify a solution).

• How to stop this circular error throwing and update the machine?

Please add apt-cache policy containerd docker.io to your question.

Here it is:

:~# apt-cache policy containerd docker.io
containerd:
    Installed:  1.5.9-0ubuntu1~18.04.2
    Candidate:  1.5.9-0ubuntu1~18.04.2
    Version table:
    *** 1.5.9-0ubuntu1~18.04.2 500
            500 http://br.archive.ubuntu.com/ubuntu bionic-updates/universe amd64 Packages
            500 http://security.ubuntu.com/ubuntu bionic-security/universe amd64 Packages
            100 /var/lib/dpkg/status
        0.2.5-0ubuntu2 500
            500 http://br.archive.ubuntu.com/ubuntu bionic/universe amd64 Packages
docker.io:
    Installed:  18.09.7-0ubuntu1~16.04.7
    Candidate:  20.10.12-0ubuntu1~18.04.1
    Version table:
        20.10.12-0ubuntu2~18.04.1 500
            500 http://br.archive.ubuntu.com/ubuntu bionic-updates/universe amd64 Packages
        20.10.7-0ubuntu5~18.04.3 500
            500 http://security.ubuntu.com/ubuntu bionic-security/universe amd64 Packages
    *** 18.09.7-0ubuntu1~16.04.7 100
            100 /var/lib/dpkg/status
        17.12.1-0ubuntu1 100
            500 http://br.archive.ubuntu.com/ubuntu bionic/universe amd64 Packages

Try apt install --reinstall docker.io=20.10.12-0ubuntu1~18.04.1

Error, similar, but more detailed than the one returned by apt --fix-broken install:

dpkg: error processing archive /var/cache/apt/archives/docker.io_20.10.12-0ubuntu2~18.04.1_amd64.deb (--unpack):
    new docker.io package pre-installation script subprocess returned error exit status 1
Errors were encountered while processing:
    /var/cache/apt/archives/docker.io_20.10.12-0ubuntu2~18.04.1_amd64.deb
E: Sub-process /usr/bin/dpkg/ returned an error code (1)

Try apt upgrade docker.io.

Error, the same previously returned by apt update and apt autoremove:

You might want to run 'apt --fix-broken install' to correct these.
The following packages have unmet dependencies:
    containerd: Breaks: docker.io (< 19.03.13-0ubuntu4) but 18.09.7-0ubuntu1~16.04.7 is installed
E: Unmet dependencies. Try 'apt --fix-broken install' with no packages (or specify a solution).