异色边

题目描述

夏天遇见的一切，都是属于浪漫的刚刚好

Orange 有 $n$ 个点，标号从 $1$ 到 $n$，每个点都有一个颜色（红色或蓝色）。Orange 现在希望用 $n$ 条边将这 $n$ 个点连接起来，使得其构成一个图，并且此图是无重边的连通图。Orange 认为异色更为浪漫，所以 Orange 希望构建的图上异色边的数量尽可能多。

请输出一个边序列描述图，使得图无重边且连通，并且其中异色边的数量最大，如果存在多种输出方案符合题意，输出任意一种均可。

异色边：一条边所连接的两个端点颜色不同。

输入格式

数据包含多组测试数据，第一行一个样例数 $T$ $(1\le T \le 10^5)$。

对于每组测试数据：

第一行一个整数 $n$ $(3\le n \le 3 \times 10^5)$，表示图上的点数。

接下来一行长度为 $n$ 的 $01$字符串 $s$，$s_i=0$ 表示 $i$ 点染为蓝色，$s_i=1$ 表示 $i$ 点染为红色。

对于所有样例保证 $\sum n \le 3\times 10^5$。

输出格式

对于每个样例：输出 $n$ 行，第 $i$ 行两个整数 $u_i,v_i$，表示第 $i$ 条边连接 $u_i$ 和 $v_i$ 点，请确保以此方式描述的图无重边且连通，并且其中异色边的数量最大，方可认为回答正确。共输出 $\sum n$ 行。

样例 #1

样例输入 #1

3
5
10100
3
000
4
1000

样例输出 #1

1 2
1 4
3 5
2 3
4 3
1 3
3 2
2 1
1 2
1 3
1 4
3 4

提示

第一组测试数据一种可能的构造方案。