CF1141D Colored Boots

有 $n$ 只左靴和 $n$ 只右靴。每只靴子都有一个颜色，用小写拉丁字母或问号（'?'）表示。因此，给定两个长度为 $n$ 的字符串 $l$ 和 $r$。字符 $l_i$ 表示第 $i$ 只左靴的颜色，字符 $r_i$ 表示第 $i$ 只右靴的颜色。 小写拉丁字母表示具体的颜色，而问号（'?'）表示不确定的颜色。两个具体颜色只有在完全相同时才兼容。不确定的颜色可以与任何（具体或不确定）颜色兼容。 例如，以下颜色对是兼容的：('f', 'f')、('?', 'z')、('a', '?') 和 ('?', '?')。以下颜色对不兼容：('f', 'g') 和 ('a', 'z')。 请计算最多可以组成多少对兼容的左右靴子，每对包含一只左靴和一只右靴，并且它们的颜色兼容。 输出最多的兼容对数以及这些配对的具体方案。每只靴子最多只能属于一对。

第一行包含一个整数 $n$（$1 \le n \le 150000$），表示每只脚的靴子数量（即左靴和右靴的数量）。 第二行包含长度为 $n$ 的字符串 $l$。只包含小写拉丁字母或问号。第 $i$ 个字符表示第 $i$ 只左靴的颜色。 第三行包含长度为 $n$ 的字符串 $r$。只包含小写拉丁字母或问号。第 $i$ 个字符表示第 $i$ 只右靴的颜色。

输出 $k$ —— 最大的兼容左右靴配对数，即每对包含一只左靴和一只右靴，并且它们的颜色兼容。 接下来的 $k$ 行，每行输出一对 $a_j, b_j$（$1 \le a_j, b_j \le n$）。第 $j$ 行输出第 $j$ 对中左靴的编号 $a_j$ 和右靴的编号 $b_j$。所有 $a_j$ 必须互不相同，所有 $b_j$ 也必须互不相同。 如果有多种最优方案，输出任意一种即可。

由 ChatGPT 4.1 翻译