Omkar and Pies

题意翻译

给定两个长度为 $k$ 的 $01$ 串，分别是起始串和目标串。 依次给出 $n$ 个可选操作，第 $j$ 个操作 $a_j,b_j$ 表示交换起始串的 $a_j$ 位置与 $b_j$ 位置。 你需要选择操作序列中其中连续的一段操作依次按顺序执行，并且选择的操作数量不小于 $m$ 。 你需要让操作完成后的串与目标串对应相同的位置数量尽可能多。 输出最大数量与你选取操作的区间（若有多种方案输出任意一个即可）。

题目描述

Omkar has a pie tray with $ k $ ( $ 2 \leq k \leq 20 $ ) spots. Each spot in the tray contains either a chocolate pie or a pumpkin pie. However, Omkar does not like the way that the pies are currently arranged, and has another ideal arrangement that he would prefer instead. To assist Omkar, $ n $ elves have gathered in a line to swap the pies in Omkar's tray. The $ j $ -th elf from the left is able to swap the pies at positions $ a_j $ and $ b_j $ in the tray. In order to get as close to his ideal arrangement as possible, Omkar may choose a contiguous subsegment of the elves and then pass his pie tray through the subsegment starting from the left. However, since the elves have gone to so much effort to gather in a line, they request that Omkar's chosen segment contain at least $ m $ ( $ 1 \leq m \leq n $ ) elves. Formally, Omkar may choose two integers $ l $ and $ r $ satisfying $ 1 \leq l \leq r \leq n $ and $ r - l + 1 \geq m $ so that first the pies in positions $ a_l $ and $ b_l $ will be swapped, then the pies in positions $ a_{l + 1} $ and $ b_{l + 1} $ will be swapped, etc. until finally the pies in positions $ a_r $ and $ b_r $ are swapped. Help Omkar choose a segment of elves such that the amount of positions in Omkar's final arrangement that contain the same type of pie as in his ideal arrangement is the maximum possible. Note that since Omkar has a big imagination, it might be that the amounts of each type of pie in his original arrangement and in his ideal arrangement do not match.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ m $ , and $ k $ ( $ 1 \leq m \leq n \leq 10^6 $ and $ 2 \leq k \leq 20 $ ) — the number of elves, the minimum subsegment length, and the number of spots in Omkar's tray respectively. The second and third lines each contain a string of length $ k $ consisting of $ 0 $ s and $ 1 $ s that represent initial arrangement of pies and ideal arrangement of pies; the $ j $ -th character in each string is equal to $ 0 $ if the $ j $ -th spot in the arrangement contains a chocolate pie and is equal to $ 1 $ if the $ j $ -th spot in the arrangement contains a pumpkin pie. It is not guaranteed that the two strings have the same amount of $ 0 $ s or the same amount of $ 1 $ s. $ n $ lines follow. The $ j $ -th of these lines contains two integers $ a_j $ and $ b_j $ ( $ 1 \leq a_j, b_j \leq k $ , $ a_j \neq b_j $ ) which indicate that the $ j $ -th elf from the left can swap the pies at positions $ a_j $ and $ b_j $ in the tray.

输出格式

Output two lines. The first line should contain a single integer $ s $ ( $ 0 \leq s \leq k $ ) equal to the amount of positions that contain the same type of pie in Omkar's final arrangement and in Omkar's ideal arrangement; $ s $ should be the maximum possible. The second line should contain two integers $ l $ and $ r $ satisfying $ 1 \leq l \leq r \leq n $ and $ r - l + 1 \geq m $ , indicating that Omkar should pass his tray through the subsegment $ l, l + 1, \dots, r $ to achieve a final arrangement with $ s $ positions having the same type of pie as his ideal arrangement. If there are multiple answers you may output any of them.

输入输出样例

输入样例 #1

4 2 5
11000
00011
1 3
3 5
4 2
3 4

输出样例 #1

5
1 3

输入样例 #2

4 3 5
11000
00011
1 3
1 5
2 4
1 5

输出样例 #2

3
1 4

说明

In the first test case, the swaps will go like this: - Swap $ 1 $ and $ 3 $ : 11000 becomes 01100 - Swap $ 3 $ and $ 5 $ : 01100 becomes 01001 - Swap $ 4 $ and $ 2 $ : 01001 becomes 00011 The final arrangement is the same as the ideal arrangement 00011, so there are $ 5 $ positions with the same type of pie, which is optimal. In the second test case, the swaps will go like this: - Swap $ 1 $ and $ 3 $ : 11000 becomes 01100 - Swap $ 1 $ and $ 5 $ : 01100 becomes 01100 - Swap $ 4 $ and $ 2 $ : 01100 becomes 00110 - Swap $ 1 $ and $ 5 $ : 00110 becomes 00110 The final arrangement has $ 3 $ positions with the same type of pie as the ideal arrangement 00011, those being positions $ 1 $ , $ 2 $ , and $ 4 $ . In this case the subsegment of elves $ (l, r) = (2, 3) $ is more optimal, but that subsegment is only length $ 2 $ and therefore does not satisfy the constraint that the subsegment be of length at least $ m = 3 $ .