Monotonic

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> PLL;
 
const ll INF = 1000000000000000LL;
 
ll n;
 
template<typename T>
void print_vector(vector<T> & v) {
  for (auto x : v) {
    cout << x << " ";
  }
}
 
const ll MAXK = 1000;
const ll TRY = 1000;
 
ll solve() {
  ll n, m;
  cin >> n >> m;
 
  vector<PLL> pr(m);
  for (int i=0; i<m; i++) {
    cin >> pr[i].first;
    cin >> pr[i].second;
    pr[i].first--;
    pr[i].second--;
  }
 
  ll maxk = 0;
  for (int ii=0; ii<TRY; ii++) {
    vector<ll> x (n);
    for (int i=0; i<n; i++) {
      x[i] = rand();
    }
 
    ll k = 0;
    while (k < MAXK) {
      k++;
      for (auto p : pr) {
	if (x[p.first] > x[p.second]) {
	  swap(x[p.first], x[p.second]);
	}
      }
 
      bool sorted = true;
      for (int i=0; i<n-1; i++) {
	sorted &= (x[i] <= x[i+1]);
      }
 
      if (sorted) { break; }
      
    }
    maxk = max(k, maxk);
    if (maxk == MAXK) { break; }
  }
 
  if (maxk == MAXK) { return -1; } else { return maxk; }
}
 
int main() {
 
  cin.tie(NULL);
  std::ios::sync_with_stdio(false);
 
  ll t;
  cin >> t;
  for (int i=0; i<t; i++) {
    cout << solve() << endl;
  }
  
  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