#include <bits/stdc++.h>
#define ll long long
#define el cout << '\n'
#define ii pair<int, int>
#define fi first
#define se second
using namespace std;
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
ll random(ll l, ll r)
{
return rd() % (r - l + 1) + l;
}
void makeTest()
{
ofstream cout("TAPPHUDINH.INP");
int t = random(1, 36);
cout << t, el;
while (t--)
{
int n = random(2, 36);
int m = random(0, (n * (n - 1))/2);
// int m = 0;
int MOD = random(1e8, 1e9);
cout << n << ' ' << m << ' ' << MOD, el;
for (int i = 1; i <= n; i++)
cout << random(1, 1e9) << ' ';
el;
set<ii> s;
while (s.size() < m)
{
int x, y;
do
{
x = random(1, n);
y = random(1, n);
} while (x == y);
if (x > y) swap(x, y);
s.insert({x, y});
};
for (ii p : s)
cout << p.fi << ' ' << p.se, el;
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
for (int i = 1; i <= 1e5; i++)
{
makeTest();
system("TAPPHUDINH.EXE");
system("TAPPHUDINH_TRAU.EXE");
if (system("fc TAPPHUDINH.OUT TAPPHUDINH_TRAU.OUT"))
{
cerr << i << " WRONG\n";
break;
}
cerr << i << " PASSED\n";
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CgojZGVmaW5lIGxsIGxvbmcgbG9uZwojZGVmaW5lIGVsIGNvdXQgPDwgJ1xuJwojZGVmaW5lIGlpIHBhaXI8aW50LCBpbnQ+CiNkZWZpbmUgZmkgZmlyc3QKI2RlZmluZSBzZSBzZWNvbmQKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgptdDE5OTM3XzY0IHJkKGNocm9ubzo6c3RlYWR5X2Nsb2NrOjpub3coKS50aW1lX3NpbmNlX2Vwb2NoKCkuY291bnQoKSk7CgpsbCByYW5kb20obGwgbCwgbGwgcikKewogICAgcmV0dXJuIHJkKCkgJSAociAtIGwgKyAxKSArIGw7Cn0Kdm9pZCBtYWtlVGVzdCgpCnsKICAgIG9mc3RyZWFtIGNvdXQoIlRBUFBIVURJTkguSU5QIik7CiAgICBpbnQgdCA9IHJhbmRvbSgxLCAzNik7CiAgICBjb3V0IDw8IHQsIGVsOwogICAgd2hpbGUgKHQtLSkKICAgIHsKICAgICAgICBpbnQgbiA9IHJhbmRvbSgyLCAzNik7CiAgICAgICAgaW50IG0gPSByYW5kb20oMCwgKG4gKiAobiAtIDEpKS8yKTsKICAgICAgICAvLyBpbnQgbSA9IDA7CiAgICAgICAgaW50IE1PRCA9IHJhbmRvbSgxZTgsIDFlOSk7CiAgICAgICAgY291dCA8PCBuIDw8ICcgJyA8PCBtIDw8ICcgJyA8PCBNT0QsIGVsOwogICAgICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG47IGkrKykKICAgICAgICAgICAgY291dCA8PCByYW5kb20oMSwgMWU5KSA8PCAnICc7CiAgICAgICAgZWw7CiAgICAgICAgc2V0PGlpPiBzOwogICAgICAgIHdoaWxlIChzLnNpemUoKSA8IG0pCiAgICAgICAgewogICAgICAgICAgICBpbnQgeCwgeTsKICAgICAgICAgICAgZG8KICAgICAgICAgICAgewogICAgICAgICAgICAgICAgeCA9IHJhbmRvbSgxLCBuKTsKICAgICAgICAgICAgICAgIHkgPSByYW5kb20oMSwgbik7CiAgICAgICAgICAgIH0gd2hpbGUgKHggPT0geSk7CiAgICAgICAgICAgIGlmICh4ID4geSkgc3dhcCh4LCB5KTsKICAgICAgICAgICAgcy5pbnNlcnQoe3gsIHl9KTsKICAgICAgICB9OwogICAgICAgIGZvciAoaWkgcCA6IHMpCiAgICAgICAgICAgIGNvdXQgPDwgcC5maSA8PCAnICcgPDwgcC5zZSwgZWw7CiAgICB9Cn0KCmludCBtYWluKCkKewogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTsgY2luLnRpZSgwKTsgY291dC50aWUoMCk7CiAgICAKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IDFlNTsgaSsrKQogICAgewogICAgICAgIG1ha2VUZXN0KCk7CiAgICAgICAgc3lzdGVtKCJUQVBQSFVESU5ILkVYRSIpOwogICAgICAgIHN5c3RlbSgiVEFQUEhVRElOSF9UUkFVLkVYRSIpOwogICAgICAgIGlmIChzeXN0ZW0oImZjIFRBUFBIVURJTkguT1VUIFRBUFBIVURJTkhfVFJBVS5PVVQiKSkKICAgICAgICB7CiAgICAgICAgICAgIGNlcnIgPDwgaSA8PCAiIFdST05HXG4iOwogICAgICAgICAgICBicmVhazsKICAgICAgICB9CiAgICAgICAgY2VyciA8PCBpIDw8ICIgUEFTU0VEXG4iOwogICAgfQp9