#include using namespace std; using ll = long long; #define all(a) (a).begin(), (a).end() #define pb push_back #define fi first #define se second mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count()); const ll MOD1000000007 = 1000000007; const ll MOD998244353 = 998244353; const ll MOD[3] = {999727999, 1070777777, 1000000007}; const ll LINF = 1LL << 60LL; const int IINF = (1 << 30) - 2; template struct edge{ int from; int to; T cost; int id; edge(){} edge(int to, T cost=1) : from(-1), to(to), cost(cost){} edge(int from, int to, T cost) : from(from), to(to), cost(cost) {} edge(int from, int to, T cost, int id) : from(from), to(to), cost(cost), id(id){} void reverse(){swap(from, to);} }; template struct edges : std::vector>{ void sort(){ std::sort( (*this).begin(), (*this).end(), [](const edge& a, const edge& b){ return a.cost < b.cost; } ); } }; template struct graph : std::vector>{ private: int n = 0; int m = 0; edges es; bool dir; public: graph(int n, bool dir) : n(n), dir(dir){ (*this).resize(n); } void add_edge(int from, int to, T cost=1){ if(dir){ es.push_back(edge(from, to, cost, m)); (*this)[from].push_back(edge(from, to, cost, m++)); }else{ if(from > to) swap(from, to); es.push_back(edge(from, to, cost, m)); (*this)[from].push_back(edge(from, to, cost, m)); (*this)[to].push_back(edge(to, from, cost, m++)); } } int get_vnum(){ return n; } int get_enum(){ return m; } bool get_dir(){ return dir; } edge get_edge(int i){ return es[i]; } edges get_edge_set(){ return es; } }; template struct redge{ int from, to; T cap, cost; int rev; redge(int to, T cap, T cost=(T)(1)) : from(-1), to(to), cap(cap), cost(cost){} redge(int to, T cap, T cost, int rev) : from(-1), to(to), cap(cap), cost(cost), rev(rev){} }; template using Edges = vector>; template using weighted_graph = vector>; template using tree = vector>; using unweighted_graph = vector>; template using residual_graph = vector>>; template static vector> decompose_maximal_cycles(graph &G){ int n = G.get_vnum(); // the number of vertices int m = G.get_enum(); // the number of edges vector visited(n, false); // visited flag vector> cycles; // the set of cycles vector idx(n, -1); // the index of the edge vector vst; // stack maintaining the vertices for(int r=0; r cyc; cyc.push_back(e.id); while(v != e.to){ vst.pop_back(); visited[v] = false; v = vst.back(); cyc.push_back(G[v][idx[v]].id); } reverse(cyc.begin(), cyc.end()); cycles.push_back(cyc); }else{ visited[e.to] = true; vst.push_back(e.to); } } visited[r] = false; } return cycles; } void solve(){ int n, m; cin >> n >> m; graph G(n, true); for(int i=0; i> u >> v; G.add_edge(u-1, v-1); } auto cycles = decompose_maximal_cycles(G); vector rest(m, true); int cnt = m; for(auto cyc : cycles){ for(auto i : cyc){ cnt--; rest[i] = false; } } cout << n << ' ' << cnt << '\n'; for(int i=0; i> T; while(T--) solve(); }