#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<sstream>#include<string>#include<cmath>#include<cctype>#include<cstdlib>#include<vector>#include<queue>#include<stack>#include<list>#include<set>#include<map>#define mp make_pair#define pb push_back#define fi first#define se secondusing namespace std;const int maxn(5 + 50000);int n,flag;int ans_cnt, ans_st, ans_en;vector<int>adj[maxn];int indd,dfn[maxn],low[maxn];int sta[maxn],numsta;bool insta[maxn];int id[maxn],numid;int id_min[maxn];int sccsize[maxn];void dfs(int a){ dfn[a] = low[a] = ++indd; insta[a] = true; sta[++numsta] = a; int s=adj[a].size(),f,b; for(f=0; f < s; f++) { b = adj[a].at(f); if(!dfn[b]) { dfs(b); low[a] = min(low[a], low[b]); } else if(insta[b]) low[a] = min(low[a], dfn[b]); } if(dfn[a] == low[a]) { numid++; id_min[numid] = maxn; sccsize[numid] = 0; int tmin=maxn, tmin2=maxn; do { b = sta[numsta--];; id[b] = numid; insta[b] = false; id_min[numid] = min(id_min[numid], b); sccsize[numid]++; if(b < tmin) { tmin2=tmin; tmin=b; } else if(b < tmin2) tmin2 = b; }while(b-a); if(sccsize[numid] > 1) { if(ans_cnt < sccsize[numid]) { ans_cnt = sccsize[numid]; ans_st = tmin; ans_en = tmin2; } else if(ans_cnt == sccsize[numid] && ans_st > tmin) { ans_st = tmin; ans_en = tmin2; } else if(ans_cnt == sccsize[numid] && ans_st == tmin) ans_en = min(ans_en, tmin2); flag=1; } }}void Tarjan(){ indd = numsta = numid = 0; memset(dfn, 0, sizeof dfn); memset(insta, false, sizeof insta); for(int e=1; e <= n; e++) if(!dfn[e]) dfs(e);}vector<int>adj22[maxn];int inde[maxn],outde[maxn];void rebuildGraph(){ memset(inde, 0, sizeof inde); memset(outde, 0, sizeof outde); int e,f,s; for(e=1; e <= n; e++) adj22[e].clear(); for(e=1; e <= n; e++) for(s=adj[e].size(), f=0; f < s; f++) if(id[e] != id[adj[e].at(f)]) { adj22[id_min[id[e]]].pb(id_min[id[adj[e].at(f)]]); inde[id_min[id[adj[e].at(f)]]]++; outde[id_min[id[e]]]++; }}int now_cnt[maxn],now_index[maxn],cx[maxn];void TopSort(){ numsta = 0; int e; for(e=1; e <= n; e++) now_index[e]=maxn; for(e=1; e <= n; e++) if(!inde[e] && outde[e]) sta[++numsta] = e, now_index[e]=id_min[id[e]]; for(e=1; e <= numid; e++) { now_cnt[id_min[e]] = sccsize[e]; cx[id_min[e]] = sccsize[e]; } while(numsta) { int now=sta[numsta--]; int s,f,b; for(s=adj22[now].size(),f=0; f < s; f++) { b = adj22[now].at(f); if(now_cnt[now]+cx[b] > now_cnt[b]) { now_cnt[b] = now_cnt[now]+cx[b]; now_index[b] = now_index[now]; } else if(now_cnt[now]+cx[b] == now_cnt[b]) now_index[b] = min(now_index[now], now_index[b]); if(!outde[b]) { if(ans_cnt < now_cnt[b]) { ans_cnt = now_cnt[b]; ans_st = b; ans_en = now_index[b]; flag=0; } else if(ans_cnt == now_cnt[b] &&ans_st!=b) { if(flag) { if(ans_st>b) { ans_st = b; ans_en = now_index[b]; flag=0; } if(ans_st>now_index[b]) { ans_st=now_index[b]; ans_en=b; flag=1; } } else { if(ans_st>b) { ans_st=b; ans_en=now_index[b]; } } } else if(ans_cnt == now_cnt[b] && ans_st == b&&ans_en>now_index[b]) ans_en = now_index[b],flag=0; } if(--inde[b] == 0) sta[++numsta] = b; } } if(!flag) cout<<ans_cnt<<"n"<<ans_st<<" "<<ans_en<<"n"; else cout<<ans_cnt<<"n"<<"1 2"<<endl;}void cyh(){ flag=0; Tarjan(); rebuildGraph(); TopSort();}int main(){ int test,st,en,e,m; for(cin>>test; test--; ) { ans_cnt=0, ans_st=maxn, ans_en=maxn; cin>>n>>m; if(m == 0) { puts("1"); puts("1 2"); continue; } for(e=1; e <= n; e++) adj[e].clear(); while(m--) { scanf("%d %d", &st,&en); if(st-en) adj[st].pb(en); } cyh(); } return 0;}
