/* in the name of Anton */ /* Compete against Yourself. Author - Aryan (@aryanc403) Atcoder library - https://atcoder.github.io/ac-library/production/document_en/ */ #include <algorithm> #include <cassert> #include <vector> #include <algorithm> #include <utility> #include <vector> #include <algorithm> #include <utility> #include <vector> namespace atcoder { namespace internal { template <class E> struct csr { std::vector<int> start; std::vector<E> elist; explicit csr(int n, const std::vector<std::pair<int, E>>& edges) : start(n + 1), elist(edges.size()) { for (auto e : edges) { start[e.first + 1]++; } for (int i = 1; i <= n; i++) { start[i] += start[i - 1]; } auto counter = start; for (auto e : edges) { elist[counter[e.first]++] = e.second; } } }; } // namespace internal } // namespace atcoder namespace atcoder { namespace internal { struct scc_graph { public: explicit scc_graph(int n) : _n(n) {} int num_vertices() { return _n; } void add_edge(int from, int to) { edges.push_back({from, {to}}); } std::pair<int, std::vector<int>> scc_ids() { auto g = csr<edge>(_n, edges); int now_ord = 0, group_num = 0; std::vector<int> visited, low(_n), ord(_n, -1), ids(_n); visited.reserve(_n); auto dfs = [&](auto self, int v) -> void { low[v] = ord[v] = now_ord++; visited.push_back(v); for (int i = g.start[v]; i < g.start[v + 1]; i++) { auto to = g.elist[i].to; if (ord[to] == -1) { self(self, to); low[v] = std::min(low[v], low[to]); } else { low[v] = std::min(low[v], ord[to]); } } if (low[v] == ord[v]) { while (true) { int u = visited.back(); visited.pop_back(); ord[u] = _n; ids[u] = group_num; if (u == v) break; } group_num++; } }; for (int i = 0; i < _n; i++) { if (ord[i] == -1) dfs(dfs, i); } for (auto& x : ids) { x = group_num - 1 - x; } return {group_num, ids}; } std::vector<std::vector<int>> scc() { auto ids = scc_ids(); int group_num = ids.first; std::vector<int> counts(group_num); for (auto x : ids.second) counts[x]++; std::vector<std::vector<int>> groups(ids.first); for (int i = 0; i < group_num; i++) { groups[i].reserve(counts[i]); } for (int i = 0; i < _n; i++) { groups[ids.second[i]].push_back(i); } return groups; } private: int _n; struct edge { int to; }; std::vector<std::pair<int, edge>> edges; }; } // namespace internal } // namespace atcoder namespace atcoder { struct scc_graph { public: scc_graph() : internal(0) {} explicit scc_graph(int n) : internal(n) {} void add_edge(int from, int to) { int n = internal.num_vertices(); assert(0 <= from && from < n); assert(0 <= to && to < n); internal.add_edge(from, to); } std::vector<std::vector<int>> scc() { return internal.scc(); } private: internal::scc_graph internal; }; } // namespace atcoder #ifdef ARYANC403 #include <header.h> #else #pragma GCC optimize ("Ofast") #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") //#pragma GCC optimize ("-ffloat-store") #include<bits/stdc++.h> #define dbg(args...) 42; #endif // y_combinator from @neal template https://codeforces.com/contest/1553/submission/123849801 // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html template<class Fun> class y_combinator_result { Fun fun_; public: template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {} template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); } }; template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); } using namespace std; #define fo(i,n) for(i=0;i<(n);++i) #define repA(i,j,n) for(i=(j);i<=(n);++i) #define repD(i,j,n) for(i=(j);i>=(n);--i) #define all(x) begin(x), end(x) #define sz(x) ((lli)(x).size()) #define pb push_back #define mp make_pair #define X first #define Y second #define endl "\n" typedef long long int lli; typedef long double mytype; typedef pair<lli,lli> ii; typedef vector<ii> vii; typedef vector<lli> vi; const auto start_time = std::chrono::high_resolution_clock::now(); void aryanc403() { #ifdef ARYANC403 auto end_time = std::chrono::high_resolution_clock::now(); std::chrono::duration<double> diff = end_time-start_time; cerr<<"Time Taken : "<<diff.count()<<"\n"; #endif } long long readInt(long long l, long long r, char endd) { long long x=0; int cnt=0; int fi=-1; bool is_neg=false; while(true) { char g=getchar(); if(g=='-') { assert(fi==-1); is_neg=true; continue; } if('0'<=g&&g<='9') { x*=10; x+=g-'0'; if(cnt==0) { fi=g-'0'; } cnt++; assert(fi!=0 || cnt==1); assert(fi!=0 || is_neg==false); assert(!(cnt>19 || ( cnt==19 && fi>1) )); } else if(g==endd) { if(is_neg) { x=-x; } assert(l<=x&&x<=r); return x; } else { assert(false); } } } string readString(int l, int r, char endd) { string ret=""; int cnt=0; while(true) { char g=getchar(); assert(g!=-1); if(g==endd) { break; } cnt++; ret+=g; } assert(l<=cnt&&cnt<=r); return ret; } long long readIntSp(long long l, long long r) { return readInt(l,r,' '); } long long readIntLn(long long l, long long r) { return readInt(l,r,'\n'); } string readStringLn(int l, int r) { return readString(l,r,'\n'); } string readStringSp(int l, int r) { return readString(l,r,' '); } void readEOF(){ assert(getchar()==EOF); } vi readVectorInt(int n,lli l,lli r){ vi a(n); for(int i=0;i<n-1;++i) a[i]=readIntSp(l,r); a[n-1]=readIntLn(l,r); return a; } bool isBinaryString(const string s){ for(auto x:s){ if('0'<=x&&x<='1') continue; return false; } return true; } // #include<atcoder/dsu> // vector<vi> readTree(const int n){ // vector<vi> e(n); // atcoder::dsu d(n); // for(lli i=1;i<n;++i){ // const lli u=readIntSp(1,n)-1; // const lli v=readIntLn(1,n)-1; // e[u].pb(v); // e[v].pb(u); // d.merge(u,v); // } // assert(d.size(0)==n); // return e; // } const lli INF = 0xFFFFFFFFFFFFFFFL; lli seed; mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count()); inline lli rnd(lli l=0,lli r=INF) {return uniform_int_distribution<lli>(l,r)(rng);} class CMP {public: bool operator()(ii a , ii b) //For min priority_queue . { return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y )); }}; void add( map<lli,lli> &m, lli x,lli cnt=1) { auto jt=m.find(x); if(jt==m.end()) m.insert({x,cnt}); else jt->Y+=cnt; } void del( map<lli,lli> &m, lli x,lli cnt=1) { auto jt=m.find(x); if(jt->Y<=cnt) m.erase(jt); else jt->Y-=cnt; } bool cmp(const ii &a,const ii &b) { return a.X<b.X||(a.X==b.X&&a.Y<b.Y); } const lli mod = 1000000007L; // const lli maxN = 1000000007L; lli T,n,i,j,k,in,cnt,l,r,u,v,x,y; lli m; string s; vi a; //priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue . int main(void) { ios_base::sync_with_stdio(false);cin.tie(NULL); // freopen("txt.in", "r", stdin); // freopen("txt.out", "w", stdout); // cout<<std::fixed<<std::setprecision(35); T=readIntLn(1,5e4); lli sumNM = 1e6; while(T--) { n=readIntLn(1,min(200000LL,sumNM)); sumNM-=n; m=readIntLn(0,min({400000LL,sumNM,n*(n-1)})); vector<bool> vis(n,true); lli cnt=n; atcoder::scc_graph g(n); while(m--){ const lli u=readIntSp(1,n)-1; const lli v=readIntLn(1,n)-1; assert(u!=v); g.add_edge(u, v); cnt-=vis[u]; vis[u]=false; } if(sz(g.scc())!=n) cnt=0; cout<<cnt-1<<endl; } aryanc403(); readEOF(); return 0; }