306567: CF1215C. Swap Letters
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Swap Letters
题意翻译
### 题目描述 ``Monocarp``有两个长度相等的,里面只有字母``a``和``b``的字符串$s,t$。 ``Monocarp``想要使这两个字符串相等。他可以执行以下操作任意次:指定两个下标$pos1,pos2$,交换$s_{pos1}$和$t_{pos2}$。 你需要确定``Monocarp``使这两个串变得相等所需要的最小操作次数,并且输出任意一个这样的步数最少的操作序列。或者说这两个串不可能变得相等。 ### 输入格式 第一行是一个整数$n(1\le n\le 2*10^5)$表示$s,t$的长度。 第二行一个只包含字母``a,b``的长度为$n$的字符串$s$。 第三行一个只包含字母``a,b``的长度为$n$的字符串$t$。 ### 输出格式 如果不可能使这两个串相等,输出``-1``。 否则,第一行输出最小操作步数$k$,然后再输出$k$行,每行两个整数,表示你在这一次进行操作时所指定的$pos1$和$pos2$。 ### 说明/提示 在第一个样例中,你可以交换$s$的第三个字母,在交换$t$的第三个字母。于是$s$变为``abbb``,$t$变为``aaab``。再交换$s$的第三个字母和$t$的第二个字母即可达成目标,使得$s,t$都变成``abab``。 第二个样例中,显然不论怎么交换$s,t$都不可能相等。题目描述
Monocarp has got two strings $ s $ and $ t $ having equal length. Both strings consist of lowercase Latin letters "a" and "b". Monocarp wants to make these two strings $ s $ and $ t $ equal to each other. He can do the following operation any number of times: choose an index $ pos_1 $ in the string $ s $ , choose an index $ pos_2 $ in the string $ t $ , and swap $ s_{pos_1} $ with $ t_{pos_2} $ . You have to determine the minimum number of operations Monocarp has to perform to make $ s $ and $ t $ equal, and print any optimal sequence of operations — or say that it is impossible to make these strings equal.输入输出格式
输入格式
The first line contains one integer $ n $ $ (1 \le n \le 2 \cdot 10^{5}) $ — the length of $ s $ and $ t $ . The second line contains one string $ s $ consisting of $ n $ characters "a" and "b". The third line contains one string $ t $ consisting of $ n $ characters "a" and "b".
输出格式
If it is impossible to make these strings equal, print $ -1 $ . Otherwise, in the first line print $ k $ — the minimum number of operations required to make the strings equal. In each of the next $ k $ lines print two integers — the index in the string $ s $ and the index in the string $ t $ that should be used in the corresponding swap operation.
输入输出样例
输入样例 #1
4
abab
aabb
输出样例 #1
2
3 3
3 2
输入样例 #2
1
a
b
输出样例 #2
-1
输入样例 #3
8
babbaabb
abababaa
输出样例 #3
3
2 6
1 3
7 8