← 返回题目列表

Codeforces · 1569/A

A. 平衡子串

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

给定一个字符串 $$$s$$$,由 $$$n$$$ 个字母组成,每个字母要么是“a”,要么是“b”。字符串中的字母编号从 $$$1$$$ 到 $$$n$$$。

$$$s[l; r]$$$ 是从字符串索引 $$$l$$$ 到 $$$r$$$ 的连续字母子串。

如果字符串中字母“a”的数量等于字母“b”的数量,则该字符串被称为平衡字符串。例如,字符串“baba”和“aabbab”是平衡的,而字符串“aaab”和“b”则不是。

查找任意非空平衡子串 $$$s[l; r]$$$ 字符串 $$$s$$$。打印它的 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$)。如果没有这样的子字符串,则打印$$$-1$$$ $$$-1$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

然后是 $$$t$$$ 测试用例的描述。

测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 50$$$) — 字符串的长度。

测试用例的第二行包含一个字符串$$$s$$$,由$$$n$$$个字母组成,每个字母是'a'或'b'。

输出

对于每个测试用例,打印两个整数。如果存在非空平衡子串$$$s[l; r]$$$,然后打印 $$$l$$$ $$$r$$$ ($$$1 \le l \le r \le n$$$)。否则,打印 $$$-1$$$ $$$-1$$$。

示例

输入 #1

4
1
a
6
abbaba
6
abbaba
9
babbabbaa

输出 #1

-1 -1
1 6
3 6
2 5

注意

在第一个测试用例中没有非空平衡子字符串。

在第二个和第三个测试用例中,有多个平衡子字符串,包括整个字符串“abbaba”和子字符串“baba”。