Broken apt and python on ubuntu server: XXX ambiguity

A running Ubuntu server 20.04LTS with unattended-upgrades, appear to have broken python installation and subsequently broken apt.
That makes me unable to upgrade or install packages. It has also disrupted services that depend on python.

First noticed with sudo apt update:

$ sudo apt update
Hit:1 http://ports.ubuntu.com/ubuntu-ports focal InRelease
Hit:2 http://ports.ubuntu.com/ubuntu-ports focal-updates InRelease
Hit:3 http://ports.ubuntu.com/ubuntu-ports focal-backports InRelease
Hit:4 http://ports.ubuntu.com/ubuntu-ports focal-security InRelease
Fatal Python error: init_import_size: Failed to import the site module
Python runtime state: initialized
Traceback (most recent call last):
  File "/usr/lib/python3.8/site.py", line 175, in addpackage
    exec(line)
  File "<string>", line 1
    import sys, types, os;has_mfs = sys.version_info > (3, 5);p = os.path.join(sys._getframe(1).f_locals['sitedir'], *('zope',));importlib = has_mfs and __import__('importlib.util');has_mfs and __import__('importlib.machinery');m = has_mfs and sys.modules.setdefault('zope', importlib.util.module_from_spec(importlib.machinery.PathFinder.find_spec('zope', [os.path.dirname(p)])));m = m or sys.modules.setdefault('zope', types.ModuleType('zope'));mp = (m or []) and m.__dict__.setdefault('__path__',[]);(p not in mp) and mp.append(p)
    ^
SyntaxError: invalid syntax

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "/usr/lib/python3.8/site.py", line 597, in <module>
    main()
  File "/usr/lib/python3.8/site.py", line 584, in main
    known_paths = addsitepackages(known_paths)
  File "/usr/lib/python3.8/site.py", line 367, in addsitepackages
    addsitedir(sitedir, known_paths)
  File "/usr/lib/python3.8/site.py", line 214, in addsitedir
    addpackage(sitedir, name, known_paths)
  File "/usr/lib/python3.8/site.py", line 183, in addpackage
    print("Error processing line {:d} of {}:\n".format(n+1, fullname),
UnicodeDecodeError: 'utf-8' codec can't decode byte 0x85 in position 0: invalid start byte
Reading package lists... Done
E: Problem executing scripts APT::Update::Post-Invoke-Success 'if /usr/bin/test -w /var/lib/command-not-found/ -a -e /usr/lib/cnf-update-db; then /usr/lib/cnf-update-db > /dev/null; fi'
E: Sub-process returned an error code

Python3 appears to be broken: pastebin

$ python3
XXX ambiguity!
XXX ambiguity!
XXX ambiguity!
<65 lines repetition>
...
XXX too high nonterminal number!
XXX too high nonterminal number!
XXX too high nonterminal number!
<40 lines repetition>
Fatal Python error: init_import_size: Failed to import the site module
Python runtime state: initialized
Traceback (most recent call last):
  File "/usr/lib/python3.8/site.py", line 175, in addpackage
    exec(line)
  File "<string>", line 1
    import sys, types, os;has_mfs = sys.version_info > (3, 5);p = os.path.join(sys._getframe(1).f_locals['sitedir'], *('zope',));importlib = has_mfs and __import__('importlib.util');has_mfs and __import__('importlib.machinery');m = has_mfs and sys.modules.setdefault('zope', importlib.util.module_from_spec(importlib.machinery.PathFinder.find_spec('zope', [os.path.dirname(p)])));m = m or sys.modules.setdefault('zope', types.ModuleType('zope'));mp = (m or []) and m.__dict__.setdefault('__path__',[]);(p not in mp) and mp.append(p)
    ^
SyntaxError: invalid syntax

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "/usr/lib/python3.8/site.py", line 597, in <module>
    main()
  File "/usr/lib/python3.8/site.py", line 584, in main
    known_paths = addsitepackages(known_paths)
  File "/usr/lib/python3.8/site.py", line 367, in addsitepackages
    addsitedir(sitedir, known_paths)
  File "/usr/lib/python3.8/site.py", line 214, in addsitedir
    addpackage(sitedir, name, known_paths)
  File "/usr/lib/python3.8/site.py", line 183, in addpackage
    print("Error processing line {:d} of {}:\n".format(n+1, fullname),
UnicodeDecodeError: 'utf-8' codec can't decode byte 0x85 in position 0: invalid start byte

However, python3 --version works:

$ python3 --version
Python 3.8.10

Following packaged are marked for reinstall by dpkg:

$ sudo dpkg -l | grep ^..R
pFR cloud-init                     21.4-0ubuntu1~20.04.1             all          initialization and customization tool for cloud instances
rFR landscape-common               19.12-0ubuntu4.2                  arm64        Landscape administration system client - Common files
rFR python3-apport                 2.20.11-0ubuntu27.21              all          Python 3 library for Apport crash report handling
rFR python3-commandnotfound        20.04.5                           all          Python 3 bindings for command-not-found.
iFR python3-distupgrade            1:20.04.37                        all          manage release upgrades
iFR python3-problem-report         2.20.11-0ubuntu27.21              all          Python 3 library to handle problem reports
rFR sosreport                      4.2-1ubuntu0.20.04.1              arm64        Set of tools to gather troubleshooting data from a system
rFR ubuntu-advantage-tools         27.6~20.04.1                      arm64        management tools for Ubuntu Advantage

But unable to use apt to install any of these packages.

Tried:

• sudo dpkg --configure -a -> console log: pastebin
• Even lsb_release -a does not work: pastebin

Original post: https://stackoverflow.com/q/72339370/3125466
The question belongs here, hence the original post has been closed