English · Original
Chinese · Translation
Formal · Original
*This is the easy version of this problem.The only difference is that you can perform at most $n$ operations.*
You are given two binary strings $a$ and $b$ of the same length $n$.
You can perform the following operation:
Output any scheme to transform $a$ into $b$ by performing at most $n$ operations.If there's no such scheme,output $-1$ instead.
The first line of the input contains a single integer $t$ ($1 <= t <= 10^4$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $n$ ($1 <= n <= 2 dot.op 10^5$).
The second line contains the binary string $a$ of length $n$.
The third line contains the binary string $b$ of length $n$.
The sum of $n$ over all test cases does not exceed $2 dot.op 10^5$.
For each test case, if it is impossible to transform $a$ into $b$ by performing such operations, output $-1$.
Otherwise, output $2$ lines.
The first line should contain a single integer $m$ ($0 <= m <= n$) — the number of operations.
The second line should contain $m$ integers ($1 <= i_1, i_2, \\dots, i_m <= n$) — indices defining the operations.
It is guaranteed that if there is a way to transform $a$ into $b$, then it can be done in at most $n$ operations.
## Input
The first line of the input contains a single integer $t$ ($1 <= t <= 10^4$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $n$ ($1 <= n <= 2 dot.op 10^5$).The second line contains the binary string $a$ of length $n$.The third line contains the binary string $b$ of length $n$.The sum of $n$ over all test cases does not exceed $2 dot.op 10^5$.
## Output
For each test case, if it is impossible to transform $a$ into $b$ by performing such operations, output $-1$.Otherwise, output $2$ lines.The first line should contain a single integer $m$ ($0 <= m <= n$) — the number of operations.The second line should contain $m$ integers ($1 <= i_1, i_2, \\dots, i_m <= n$) — indices defining the operations.It is guaranteed that if there is a way to transform $a$ into $b$, then it can be done in at most $n$ operations.
[samples]
*这是本题的简单版本，唯一的区别是你可以执行至多 $n$ 次操作。*
给你两个长度均为 $n$ 的二进制字符串 $a$ 和 $b$。
你可以执行以下操作：
请输出一种方案，通过执行至多 $n$ 次操作将 $a$ 转换为 $b$。如果不存在这样的方案，则输出 $-1$。
输入的第一行包含一个整数 $t$ ($1 lt.eq t lt.eq 10^4$) —— 测试用例的数量。接下来是测试用例的描述。
每个测试用例的第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 2 dot.op 10^5$)。
第二行包含长度为 $n$ 的二进制字符串 $a$。
第三行包含长度为 $n$ 的二进制字符串 $b$。
所有测试用例的 $n$ 之和不超过 $2 dot.op 10^5$。
对于每个测试用例，如果无法通过上述操作将 $a$ 转换为 $b$，则输出 $-1$。
否则，输出两行：
第一行应包含一个整数 $m$ ($0 lt.eq m lt.eq n$) —— 操作次数。
第二行应包含 $m$ 个整数 ($1 lt.eq i_1, i_2, dots.h, i_m lt.eq n$) —— 定义操作的索引。
保证如果存在将 $a$ 转换为 $b$ 的方法，则可以在至多 $n$ 次操作内完成。
## Input
输入的第一行包含一个整数 $t$ ($1 lt.eq t lt.eq 10^4$) —— 测试用例的数量。接下来是测试用例的描述。每个测试用例的第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 2 dot.op 10^5$)。第二行包含长度为 $n$ 的二进制字符串 $a$。第三行包含长度为 $n$ 的二进制字符串 $b$。所有测试用例的 $n$ 之和不超过 $2 dot.op 10^5$。
## Output
对于每个测试用例，如果无法通过上述操作将 $a$ 转换为 $b$，则输出 $-1$。否则，输出两行：第一行应包含一个整数 $m$ ($0 lt.eq m lt.eq n$) —— 操作次数。第二行应包含 $m$ 个整数 ($1 lt.eq i_1, i_2, dots.h, i_m lt.eq n$) —— 定义操作的索引。保证如果存在将 $a$ 转换为 $b$ 的方法，则可以在至多 $n$ 次操作内完成。
[samples]
**Definitions**
Let $ t \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, t\} $:
- Let $ n_k \in \mathbb{Z} $ be the length of binary strings.
- Let $ a_k = (a_{k,1}, \dots, a_{k,n_k}) \in \{0,1\}^{n_k} $, $ b_k = (b_{k,1}, \dots, b_{k,n_k}) \in \{0,1\}^{n_k} $ be the input binary strings.
**Constraints**
1. $ 1 \le t \le 10^4 $
2. $ 1 \le n_k \le 2 \cdot 10^5 $ for each $ k $
3. $ \sum_{k=1}^t n_k \le 2 \cdot 10^5 $
**Objective**
For each test case $ k $, find a sequence of indices $ i_1, \dots, i_m \in \{1, \dots, n_k\} $ with $ 0 \le m \le n_k $, such that applying the operation (flip prefix of length $ i_j $) to $ a_k $ in order yields $ b_k $.
If no such sequence exists, output $ -1 $.
**Operation**
An operation at index $ i $ flips all bits in the prefix $ a_{k,1}, \dots, a_{k,i} $:
$ a_{k,j} \leftarrow 1 - a_{k,j} $ for all $ j \le i $.
API Response (JSON)
{
"problem": {
"name": "D2. Prefix XOR Problem(Hard Version)",
"description": {
"content": "*This is the easy version of this problem.The only difference is that you can perform at most $n$ operations.* You are given two binary strings $a$ and $b$ of the same length $n$. You can perform th",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CFD2"
},
"statements": [
{
"statement_type": "Markdown",
"content": "*This is the easy version of this problem.The only difference is that you can perform at most $n$ operations.*\n\nYou are given two binary strings $a$ and $b$ of the same length $n$.\n\nYou can perform th...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "*这是本题的简单版本，唯一的区别是你可以执行至多 $n$ 次操作。*\n\n给你两个长度均为 $n$ 的二进制字符串 $a$ 和 $b$。\n\n你可以执行以下操作：\n\n请输出一种方案，通过执行至多 $n$ 次操作将 $a$ 转换为 $b$。如果不存在这样的方案，则输出 $-1$。\n\n输入的第一行包含一个整数 $t$ ($1 lt.eq t lt.eq 10^4$) —— 测试用例的数量。接下来是测试用例...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ t \\in \\mathbb{Z} $ be the number of test cases. \nFor each test case $ k \\in \\{1, \\dots, t\\} $: \n- Let $ n_k \\in \\mathbb{Z} $ be the length of binary strings. \n- Let $ a_k = ...",
"is_translate": false,
"language": "Formal"
}
]
}