{"problem":{"name":"F. AB-Strings","description":{"content":"There are two strings _s_ and _t_, consisting only of letters _a_ and _b_. You can make the following operation several times: choose a prefix of _s_, a prefix of _t_ and swap them. Prefixes can be em","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1013F"},"statements":[{"statement_type":"Markdown","content":"There are two strings _s_ and _t_, consisting only of letters _a_ and _b_. You can make the following operation several times: choose a prefix of _s_, a prefix of _t_ and swap them. Prefixes can be empty, also a prefix can coincide with a whole string.\n\nYour task is to find a sequence of operations after which one of the strings consists only of _a_ letters and the other consists only of _b_ letters. The number of operations should be minimized.\n\n## Input\n\nThe first line contains a string _s_ (1 ≤ |_s_| ≤ 2·105).\n\nThe second line contains a string _t_ (1 ≤ |_t_| ≤ 2·105).\n\nHere |_s_| and |_t_| denote the lengths of _s_ and _t_, respectively. It is guaranteed that at least one of the strings contains at least one _a_ letter and at least one of the strings contains at least one _b_ letter.\n\n## Output\n\nThe first line should contain a single integer _n_ (0 ≤ _n_ ≤ 5·105) — the number of operations.\n\nEach of the next _n_ lines should contain two space-separated integers _a__i_, _b__i_ — the lengths of prefixes of _s_ and _t_ to swap, respectively.\n\nIf there are multiple possible solutions, you can print any of them. It's guaranteed that a solution with given constraints exists.\n\n[samples]\n\n## Note\n\nIn the first example, you can solve the problem in two operations:\n\n1.  Swap the prefix of the first string with length 1 and the prefix of the second string with length 0. After this swap, you'll have strings _ab_ and _bbb_.\n2.  Swap the prefix of the first string with length 1 and the prefix of the second string with length 3. After this swap, you'll have strings _bbbb_ and _a_.\n\nIn the second example, the strings are already appropriate, so no operations are needed.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"有两个仅由字母 _a_ 和 _b_ 组成的字符串 #cf_span[s] 和 #cf_span[t]。你可以进行以下操作若干次：选择 #cf_span[s] 的一个前缀和 #cf_span[t] 的一个前缀，并交换它们。前缀 #cf_span(class=[tex-font-style-underline], body=[可以为空])，前缀也可以与整个字符串相同。\n\n你的任务是找到一个操作序列，使得操作后其中一个字符串仅由 _a_ 组成，另一个仅由 _b_ 组成。操作次数应被 #cf_span(class=[tex-font-style-underline], body=[最小化])。\n\n第一行包含一个字符串 #cf_span[s] (#cf_span[1 ≤ |s| ≤ 2·105])。\n\n第二行包含一个字符串 #cf_span[t] (#cf_span[1 ≤ |t| ≤ 2·105])。\n\n这里 #cf_span[|s|] 和 #cf_span[|t|] 分别表示 #cf_span[s] 和 #cf_span[t] 的长度。保证至少有一个字符串包含至少一个 _a_ 字母，且至少有一个字符串包含至少一个 _b_ 字母。\n\n第一行应包含一个整数 #cf_span[n] (#cf_span[0 ≤ n ≤ 5·105]) —— 操作次数。\n\n接下来的 #cf_span[n] 行，每行包含两个用空格分隔的整数 #cf_span[ai], #cf_span[bi] —— 分别表示要交换的 #cf_span[s] 和 #cf_span[t] 的前缀长度。\n\n如果有多个可能的解，你可以输出任意一个。保证在给定约束下存在解。\n\n在第一个例子中，你可以用两步操作解决：\n\n在第二个例子中，字符串已经符合要求，因此不需要任何操作。\n\n## Input\n\n第一行包含一个字符串 #cf_span[s] (#cf_span[1 ≤ |s| ≤ 2·105])。第二行包含一个字符串 #cf_span[t] (#cf_span[1 ≤ |t| ≤ 2·105])。这里 #cf_span[|s|] 和 #cf_span[|t|] 分别表示 #cf_span[s] 和 #cf_span[t] 的长度。保证至少有一个字符串包含至少一个 _a_ 字母，且至少有一个字符串包含至少一个 _b_ 字母。\n\n## Output\n\n第一行应包含一个整数 #cf_span[n] (#cf_span[0 ≤ n ≤ 5·105]) —— 操作次数。接下来的 #cf_span[n] 行，每行包含两个用空格分隔的整数 #cf_span[ai], #cf_span[bi] —— 分别表示要交换的 #cf_span[s] 和 #cf_span[t] 的前缀长度。如果有多个可能的解，你可以输出任意一个。保证在给定约束下存在解。\n\n[samples]\n\n## Note\n\n在第一个例子中，你可以用两步操作解决：交换第一个字符串长度为 #cf_span[1] 的前缀和第二个字符串长度为 #cf_span[0] 的前缀。交换后，你将得到字符串 _ab_ 和 _bbb_。交换第一个字符串长度为 #cf_span[1] 的前缀和第二个字符串长度为 #cf_span[3] 的前缀。交换后，你将得到字符串 _bbbb_ 和 _a_。在第二个例子中，字符串已经符合要求，因此不需要任何操作。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ s, t \\in \\{a, b\\}^* $ be two input strings over the alphabet $\\{a, b\\}$.  \nLet $ n = |s| $, $ m = |t| $.  \n\n**Constraints**  \n1. $ 1 \\leq |s| \\leq 2 \\cdot 10^5 $, $ 1 \\leq |t| \\leq 2 \\cdot 10^5 $  \n2. At least one of $ s, t $ contains at least one $ a $, and at least one contains at least one $ b $.  \n\n**Objective**  \nFind a sequence of operations minimizing the number of steps, where each operation consists of selecting prefixes $ s[1..i] $ and $ t[1..j] $ (with $ 0 \\leq i \\leq |s| $, $ 0 \\leq j \\leq |t| $) and swapping them, such that after all operations:  \n- One string contains only $ a $'s,  \n- The other contains only $ b $'s.  \n\n**Output**  \nA sequence of $ n $ operations $ (a_1, b_1), (a_2, b_2), \\dots, (a_n, b_n) $, where each $ a_k \\in [0, |s|] $, $ b_k \\in [0, |t|] $, representing the prefix lengths swapped in step $ k $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1013F","tags":["constructive algorithms","strings"],"sample_group":[["bab\nbb","2\n1 0\n1 3"],["bbbb\naaa","0"]],"created_at":"2026-03-03 11:00:39"}}