Deranging Hat

#include <bits/stdc++.h>

using namespace std;

int main(){
	string s; cin >> s;
	string s2 = s;
	sort(s2.begin(), s2.end());
	int n = s.length();
	for(int i = 0; i < n; ++i){
		if(s2[i] == s[i])
			continue;
		for(int j = i+1; j < n; ++j){
			if(s2[j] == s[i]){
				if(s2[j] > s2[i])
					cout << j+1 << " " << i+1 << '\n';
				else
					cout << i+1 << " " << j+1 << '\n';
				swap(s2[j], s2[i]);
				break;
			}
		}
	}
	return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED