← 返回题目列表

Codeforces · 1141/D

D. 彩色靴子

中文机器翻译题面 查看原题

有 $$$n$$$ 左靴子和 $$$n$$$ 右靴子。每只靴子都有一种颜色,用小写拉丁字母或问号(“?”)表示。因此,您将获得两个字符串 $$$l$$$ 和 $$$r$$$,长度均为 $$$n$$$。字符$$$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$$$ 和第 $$$j$$$ 对中右靴的索引 $$$b_j$$$。所有数字 $$$a_j$$$ 应该是不同的(唯一的),所有数字 $$$b_j$$$ 应该是不同的(唯一的)。

如果有多个最佳答案,则打印其中任何一个。

示例

输入 #1

10
codeforces
dodivthree

输出 #1

5
7 8
4 9
2 2
9 10
3 1

输入 #2

7
abaca?b
zabbbcc

输出 #2

5
6 5
2 3
4 6
7 4
1 2

输入 #3

9
bambarbia
hellocode

输出 #3

0

输入#4

10
code??????
??????test

输出#4

10
6 2
1 6
7 3
3 5
4 8
9 7
5 1
2 4
10 9
8 10