Python3のUnicodeEncodeErrorについて

下記を実行し、英数字をinputすれば問題なく動作するのですが、
日本語文字列を入れると、
UnicodeEncodeError: 'utf-8' codec can't encode characters in position [txt変数に格納された文字列の該当位置開始位置から終了位置]: surrogates not allowed

type(txt): <class 'str'>
type(answer): <class 'str'>
typeを見ても、同じstr型のクラスで問題なさそうに思えます。
どう解釈されて、なぜエラーになっているのでしょうか。

bash
# エラー内容 ↓↓↓↓↓
キリンは大昔から__複数名詞__の興味の対象でした、キリンは__複数名詞__の中で一番背が買いですが、科学者たちはそのような長い__体の一部__をどうやって獲得したのか説明できません。キリンの身長は___数値__ __単位__ 近くあり、その高さのほとんどは足と__体の一部__によるものです。

type(txt):  <class 'str'>
type(mls):  <class 'str'>
__複数名詞__を入力: あういえお
type(answer):  <class 'str'>
__複数名詞__を入力: a
type(answer):  <class 'str'>
__体の一部__を入力: i
type(answer):  <class 'str'>
___数値__を入力: u
type(answer):  <class 'str'>
__単位__を入力: e
type(answer):  <class 'str'>
__体の一部__を入力: o
type(answer):  <class 'str'>


Traceback (most recent call last):
  File "17-p213.py", line 29, in <module>
    mad_libs(txt)
  File "17-p213.py", line 23, in mad_libs
    print(mls)
UnicodeEncodeError: 'utf-8' codec can't encode characters in position 8-22: surrogates not allowed

python3
#!/usr/bin/env python3.6
# encoding: utf-8

import re
import io, sys
sys.stdout = io.TextIOWrapper(sys.stdout.buffer, encoding="utf-8")

txt = """キリンは大昔から__複数名詞__の興味の対象でした、キリンは__複数名詞__の中で一番背が買いですが、科学者たちはそのような長い__体の一部__をどうやって獲得したのか説明できません。キリンの身長は___数値__ __単位__ 近くあり、その高さのほ>とんどは足と__体の一部__によるものです。
"""

def mad_libs(mls):
    hints = re.findall("__.*?__", mls)
    print("type(mls): ", type(mls))
    if hints is not None:
        for hint in hints:
            question = "{}を入力: ".format(hint)
            answer = input(question)
            print("type(answer): ", type(answer))
            # 1つだけ置換
            mls = mls.replace(hint, answer, 1)
        print("\n")
        mls = mls.replace("\n", "")
        print(mls)
    else:
        print("引数: mls が無効です")

print(txt)
print("type(txt): ", type(txt))
mad_libs(txt)

※追記:
export LC_ALL=en_US.UTF-8
をしたら日本語をinput()に渡したら動作するようになりましたが、
exportしなくてもいいように、
import io, sys
sys.stdout = io.TextIOWrapper(sys.stdout.buffer, encoding="utf-8")
を追加したのですが、なぜこのような違いが出るのでしょうか。

bash
echo $SHELL
/usr/bin/fish

fish --version
fish, version 2.7.1

echo $locale

echo $LC_ALL

export LC_ALL=en_US.UTF-8
echo $locale

echo $LC_ALL
en_US.UTF-8