Python, отправляющий электронную почту с умляутами

Я хочу создать программу на python, которая получает каждое новое непрочитанное письмо с одной из моих учетных записей электронной почты на другую учетную запись электронной почты.

Пока у меня все настроено. К сожалению, у меня действительно большие проблемы с умлаутами (ä,ö,ü). По какой-то причине я не заставляю его работать должным образом.

Вот мой код:

# -*- coding: utf-8 -*-

import os, sys
import imaplib
import email
import smtplib
from email.mime.multipart import MIMEMultipart

servername = 'SERVERNAME'
username='USERNAME'
password='PASSWORD'


mail = imaplib.IMAP4_SSL(servername)
(retcode, capabilities) = mail.login(username,password)
mail.list()
mail.select('inbox')

server_smtp = smtplib.SMTP_SSL('SMTP')

n=0
(retcode, messages) = mail.search(None, '(UNSEEN)')
if retcode == 'OK':

for num in messages[0].split() :
  n=n+1
  typ, data = mail.fetch(num,'(RFC822)')
  for response_part in data:
     if isinstance(response_part, tuple):
        original = email.message_from_string(response_part[1])

        print original['From']
        typ, data = mail.store(num,'+FLAGS','\\Seen')

        body = ""
        if original.is_multipart():
            for part in original.walk():
                ctype = part.get_content_type()
                cdispo = str(part.get('Content-Disposition'))

                if ctype == 'text/plain' and 'attachment' not in cdispo:
                    body = part.get_payload(decode=True)  # decode
                    break
                else:
                    body = original.get_payload(decode=True)

        body = body.encode('UTF-8')
        body = str(body)

        print(body)
        body = "Betreff: " + str(original['Subject']) + "\n\n\n" + body.encode('UTF-8')
        SUBJECT = original['From']

        server_smtp.login(username, password)
        msg = 'Subject: {}\n\n{}'.format(SUBJECT, body.decode('UTF-8')) 
        server_smtp.sendmail(username, 'TARGET', msg)

Например: если я хочу отправить это сообщение: "ÄäÖöÜü&ß", я получу это: "������������&�� ���"

Вы знаете, что я делаю неправильно? Я был бы очень признателен за вашу помощь!