#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define INF 1000000001LL
#define POT (1LL<<23)
#define INFL 1000000000000000099LL
#define pii pair<ll,ll>
#define ppi pair<pii,ll>
#define pip pair<ll,pii>
#define ppp pair<pii,pii>
#define vi vector<ll>
#define vii vector<pii>
#define vvi vector<vi>
#define al(x) x.begin(),x.end()
#define rev(x) reverse(al(x))
#define X 18
#define FCTCST 7
template<typename T, typename U>
pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) {
return {a.first + b.first, a.second + b.second};
}
template<typename T, typename U>
pair<T, U> operator-(const pair<T, U>& a, const pair<T, U>& b) {
return {a.first - b.first, a.second - b.second};
}
template<typename T, typename U,typename Z>
pair<T, U> operator*(const pair<T, U>& a, const Z& b) {
return {a.first*b, a.second*b};
}
template<typename T, typename U,typename Z>
pair<T, U> operator/(const pair<T, U>& a, const Z& b) {
return {a.first/b, a.second/b};
}
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
os<<"{"<<p.ff<<", "<<p.ss<<"}";
return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
os << "{";
for (size_t i = 0; i < v.size(); ++i) {
if (i) os << ", ";
os << v[i];
}
os << "}";
return os;
}
template<ll MOD=998244353>
struct mint_t{
ll x;
mint_t(ll y=0){x=y%MOD;if(x<0)x+=MOD;}
mint_t& operator+=(const mint_t& a){if((x+=a.x)>=MOD)x-=MOD;return *this;}
mint_t& operator-=(const mint_t& a){if((x+=MOD-a.x)>=MOD)x-=MOD;return *this;}
mint_t operator+(const mint_t& a)const{mint_t res(*this);return res+=a;}
mint_t operator-(const mint_t& a)const{mint_t res(*this);return res-=a;}
mint_t& operator*=(const mint_t& a){(x*=a.x)%=MOD;return *this;}
mint_t operator*(const mint_t& a)const{mint_t res(*this);return res*=a;}
mint_t fp(ll y)const{
mint_t a=1,b=x;
while(y){
if(y&1)a*=b;
b*=b;
y/=2;
}
return a;
}
mint_t& operator/=(const mint_t& a){(*this)*=a.fp(MOD-2);return *this;}
mint_t operator/(const mint_t& a)const{mint_t res(*this);return res/=a;}
};
#define mint mint_t<>
template<long long MOD>
istream& operator>>(istream& in, mint_t<MOD>& a){
ll x;
in>>x;
a=mint_t<MOD>(x);
return in;
}
template<long long MOD>
istream& operator<<(istream& out, mint_t<MOD>& a){
out<<a.x;
return out;
}
mint fct[FCTCST];
mint bnm(ll a,ll b){
if(b>a || a<0)return 0;
return fct[a]/fct[b]/fct[a-b];
}
int query(std::vector<int> x);
void answer(int a,int b);
bool dir[48][15007];
vii e;
vi g[10007],g2[10007],d[10007],g3[10007],g4[10007];
ll ak=0;
bool vs[10007];
ll lay[10007],sz[10007],dp[10007],dg[10007],nm[10007];
ll dfs(ll v,ll x,ll pop){
if(lay[v]!=x || vs[v])return 0;
vs[v]=1;
d[pop].pb(v);
sz[v]=1;
for(ll i : g2[v])sz[v]+=dfs(i,x,v);
return sz[v];
}
ll fnd(ll v,ll x){
for(ll i: d[v])if(sz[i]*2>x)return fnd(i,x);
return v;
}
void df2(ll v,ll x,ll y){
dp[v]=x;
for(ll i : d[v])df2(i,x+y,y);
}
ll mx=0;
void slv(vi v,ll it){
//cout<<v<<" "<<it<<" "<<flush;
if(v.size()<2)return;
mx=max(mx,it+3);
for(ll i: v)lay[i]=ak,vs[i]=0,d[i].clear();
ll cent=fnd(v[0],dfs(v[0],ak,10006));//cout<<cent<<endl;
ak++;
for(ll i: v)lay[i]=ak,vs[i]=0,d[i].clear();
dfs(cent,ak,10006);
ll l=0,r=d[cent].size()-1,l1=0,l2=0;
while((l1+sz[d[cent][l]])*2<=v.size())l1+=sz[d[cent][l++]];
while((l2+sz[d[cent][r]])*2<=v.size())l2+=sz[d[cent][r--]];
l--;r++;
for(ll i=0;i<3;i++){
df2(cent,0,1);
//cout<<i<<" "<<flush;
if(i==0)for(ll j=0;j<=l;j++)df2(d[cent][j],-1,-1);
if(i==1)for(ll j=l+1;j<r;j++)df2(d[cent][j],-1,-1);
if(i==2)for(ll j=r;j<d[cent].size();j++)df2(d[cent][j],-1,-1);
for(ll j : v){
for(ll k : g3[j]){
if(lay[e[k].ss]!=ak)continue;
dir[it+i][k]=(pii{dp[e[k].ff],e[k].ff}>pii{dp[e[k].ss],e[k].ss});
}
}
}
dp[cent]=-1;
for(ll j=0;j<=l;j++)df2(d[cent][j],1,0);
for(ll j=l+1;j<r;j++)df2(d[cent][j],2,0);
for(ll j=r;j<d[cent].size();j++)df2(d[cent][j],3,0);
//cout<<"xd"<<flush;
for(ll j : v){
for(ll k : g3[j]){
if(lay[e[k].ss]!=ak)continue;
if(dp[e[k].ff]!=dp[e[k].ss]){
for(ll i=it+3;i<48;i++)dir[i][k]=(dp[e[k].ff]>dp[e[k].ss]);
}
}
}
//cout<<l<<" "<<r<<"\n";
ak++;
vi v2[3];
if(l)v2[0].pb(cent);
if(l+2<r)v2[1].pb(cent);
if(r!=d[cent].size()-1)v2[2].pb(cent);
for(ll i : v){
if(i!=cent)v2[dp[i]-1].pb(i);
}
//for(ll i=0;i<3;i++)cout<<v2[i]<<endl;cout<<endl;
for(ll i=0;i<3;i++){
slv(v2[i],it+3);
}
}
void solve(int n,int m,vector<int>u,vector<int>v){
for(ll i=0;i<m;i++){
g[u[i]].pb(v[i]);
g3[u[i]].pb(i);
e.pb({u[i],v[i]});
g2[u[i]].pb(v[i]);
g2[v[i]].pb(u[i]);
}
vi v2;
for(ll i=0;i<n;i++){
v2.pb(i);
}
slv(v2,0);
ll x;
for(int i=0;i<100000000;i++){x+=i*i;}
assert(x);
vector<int>zap;
while(mx--){
zap.clear();
for(ll j=0;j<m;j++){
zap.pb(dir[mx][j]);
}
if(query(zap)){
//cout<<zap<<endl;
for(ll i=0;i<m;i++){
if(zap[i])g4[v[i]].pb(u[i]),dg[u[i]]++;
else g4[u[i]].pb(v[i]),dg[v[i]]++;
}
break;
}
}
queue<ll>q;
for(ll i=0;i<n;i++){
if(dg[i]==0)q.push(i);
}
vi ord;
ak=0;
while(q.size()){
nm[q.front()]=ak++;
ord.pb(q.front());q.pop();
for(ll i : g4[ord.back()])if(--dg[i]==0)q.push(i);
}
ll l=1,r=n-1;
while(l!=r){
ll md=(l+r+1)/2;
vector<int>za;
for(ll i=0;i<m;i++){
za.pb((nm[e[i].ff]>=md || nm[e[i].ss]>=md)^zap[i]);
}
if(query(za))r=md-1;
else l=md;
}
ll kn=l;
l=0;r=n-2;
while(l!=r){
ll md=(l+r)/2;
vector<int>za;
for(ll i=0;i<m;i++){
za.pb((nm[e[i].ff]<=md || nm[e[i].ss]<=md)^zap[i]);
}
if(query(za))l=md+1;
else r=md;
}
answer(ord[l],ord[kn]);
}
