1682D - Circular Spanning Tree - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
// #define int long long
typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e5 + 10, M = 2 * N;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
int n, m;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tc;
    cin >> tc;
    while (tc--)
    {
        cin >> n;
        string s;
        cin >> s;
        int idx, zero = 0, one = 0;
        for (int i = 0; i < n; i++)
        {
            if (s[i] == '1')
                one++;
            else
                zero++;
        }
        if (!one || one % 2 == 1)
        {
            cout << "NO\n";
            continue;
        }
        for (int i = 0; i < n; i++)
        {
            if (s[i] == '1')
            {
                idx = (i + 1) % n;
                break;
            }
        }

        // idx是1后面的结点
        cout << "YES\n";
        for (int i = (idx + 1) % n; i != idx; i = (i + 1) % n)
        {
            cout << idx + 1 << ' ' << i + 1 << '\n';
            while ((i != idx) && s[i] == '0')
            {
                cout << (i + 1) << ' ' << (i + 1) % n + 1 << '\n';
                i = (i + 1) % n;
            }
        }
    }
    return 0;
}