#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(ac) ac.begin(),ac.end()
#define task "tet"
mt19937_64 rd( chrono:: steady_clock :: now ( ) .time_since_epoch ( ) .count ( ) ) ;
int rand ( int l, int r) { return l+ rd( ) % ( r- l+ 1 ) ; }
void test_gen( ) {
ofstream cout ( task".inp" ) ;
int tc= rand ( 4 ,10 ) ;
cout << tc << '\n ' ;
while ( tc-- > 0 ) {
int n= rand ( 10 ,50 ) , m= rand ( 30 ,60 ) ;
cout << n << ' ' << m << '\n ' ;
for ( int i= 1 ; i<= m; i++ ) {
int u= rand ( 1 ,n) , v= u;
while ( u== v) v= rand ( 1 ,n) ;
cout << u << ' ' << v << ' ' << rand ( 1 ,44 ) << '\n ' ;
}
cout << '\n ' ;
}
cout .close ( ) ;
return ;
}
int32_t main( ) {
ios:: sync_with_stdio ( false ) ;
cin .tie ( 0 ) , cout .tie ( 0 ) ;
int tc= 30 ;
system ( "cls" ) ;
system ( "g++ sol.cpp -o sol.exe" ) ;
system ( "g++ brute.cpp -o brute.exe" ) ;
for ( int i= 1 ; i<= tc; i++ ) {
test_gen( ) ;
system ( "sol.exe" ) ;
system ( "brute.exe" ) ;
if ( system ( "fc " task ".out " task ".ans" ) ! = 0 ) {
cerr << "TEST " << i << ": Wrong Answer!" ;
return 0 ;
}
cerr << "TEST " << i << ": ACCEPTED!\n \n " ;
}
return 0 ;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgaW50IGxvbmcgbG9uZwojZGVmaW5lIGFsbChhYykgYWMuYmVnaW4oKSxhYy5lbmQoKQojZGVmaW5lIHRhc2sgInRldCIKbXQxOTkzN182NCByZChjaHJvbm86OnN0ZWFkeV9jbG9jazo6bm93KCkudGltZV9zaW5jZV9lcG9jaCgpLmNvdW50KCkpOwppbnQgcmFuZChpbnQgbCwgaW50IHIpIHtyZXR1cm4gbCtyZCgpJShyLWwrMSk7fQp2b2lkIHRlc3RfZ2VuKCkgewogICAgb2ZzdHJlYW0gY291dCh0YXNrIi5pbnAiKTsKICAgIGludCB0Yz1yYW5kKDQsMTApOwogICAgY291dCA8PCB0YyA8PCAnXG4nOwogICAgd2hpbGUodGMtLT4wKSB7CiAgICAgICAgaW50IG49cmFuZCgxMCw1MCksIG09cmFuZCgzMCw2MCk7CiAgICAgICAgY291dCA8PCBuIDw8ICcgJyA8PCBtIDw8ICdcbic7CiAgICAgICAgZm9yKGludCBpPTE7aTw9bTtpKyspIHsKICAgICAgICAgICAgaW50IHU9cmFuZCgxLG4pLCB2PXU7CiAgICAgICAgICAgIHdoaWxlKHU9PXYpIHY9cmFuZCgxLG4pOwogICAgICAgICAgICBjb3V0IDw8IHUgPDwgJyAnIDw8IHYgPDwgJyAnIDw8IHJhbmQoMSw0NCkgPDwgJ1xuJzsKICAgICAgICB9CiAgICAgICAgY291dCA8PCAnXG4nOwogICAgfQogICAgY291dC5jbG9zZSgpOwogICAgcmV0dXJuOwp9CmludDMyX3QgbWFpbigpIHsKICAgIGlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUoMCksIGNvdXQudGllKDApOwogICAgaW50IHRjPTMwOwogICAgc3lzdGVtKCJjbHMiKTsKICAgIHN5c3RlbSgiZysrIHNvbC5jcHAgLW8gc29sLmV4ZSIpOwogICAgc3lzdGVtKCJnKysgYnJ1dGUuY3BwIC1vIGJydXRlLmV4ZSIpOwogICAgZm9yKGludCBpPTE7aTw9dGM7aSsrKSB7CiAgICAgICAgdGVzdF9nZW4oKTsKICAgICAgICBzeXN0ZW0oInNvbC5leGUiKTsKICAgICAgICBzeXN0ZW0oImJydXRlLmV4ZSIpOwogICAgICAgIGlmKHN5c3RlbSgiZmMgIiB0YXNrICIub3V0ICIgdGFzayAiLmFucyIpICE9IDApIHsKICAgICAgICAgICAgY2VyciA8PCAiVEVTVCAiIDw8IGkgPDwgIjogV3JvbmcgQW5zd2VyISI7CiAgICAgICAgICAgIHJldHVybiAwOwogICAgICAgIH0KICAgICAgICBjZXJyIDw8ICJURVNUICIgPDwgaSA8PCAiOiBBQ0NFUFRFRCFcblxuIjsKICAgIH0KICAgIHJldHVybiAwOwp9