Monotonic

#include <bits/stdc++.h>

#define ll long long
#define lll __int128
#define pii pair<int, int>
#define M 1000000007
#define N 101
#define PB push_back
#define F first
#define S second
using namespace std;

int solve() {
	int n, m;
	cin>>n>>m;
	pii p[m];
	for (int i = 0; i < m; i++) cin>>p[i].F>>p[i].S, p[i].F--, p[i].S--;
	vector<int> t;
	for (int i = 0; i < n; i++) t.push_back(n - i);
	int ans = 0;
	for (int tt = 0; tt < 50; tt++) {
		for (int sh = 0; sh < n; sh++) {
			vector<int> c(n);
			bool sr = true;
			for (int i = 0; i < n; i++) {
				if (i) sr &= t[(i + sh) % n] > t[(i + sh - 1 + n) % n];
				c[i] = t[(i + sh) % n];
			}
			int op = 0;
			while (!sr) {
				op++;
				
				for (int i = 0; i < m; i++) {
					if (c[p[i].F] > c[p[i].S]) swap(c[p[i].F], c[p[i].S]);
				}
				
				sr = true;
				for (int i = 1; i < n; i++) {
					if (i) sr &= c[i] > c[i - 1];
				}
				if (op == n) return -1;
			}
			ans = max(op, ans);
		}
		random_shuffle(t.begin(), t.end());
	}
	return ans;
}

int main () {
	cin.sync_with_stdio(false);
	cin.tie(0);
	ll t; cin >> t;
	while(t--) cout << solve() << "\n";
}

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