/** * code generated by JHelper * More info: https://github.com/AlexeyDmitriev/JHelper * @author */ //@formatter:off #pragma GCC optimize("Ofast") #include using namespace std; // #include // using namespace atcoder; //@formatter:off #define rep(i, n) for (int i = 0; i < (n); ++i) #define drep(i, n) for (int i = (n)-1; i >= 0; --i) #define srep(i, s, t) for (int i = s; i < t; ++i) #define rng(a) a.begin(), a.end() #define rrng(a) a.rbegin(), a.rend() using ll = long long; using P = pair; using VI = vector; using VVI = vector; using VVVI = vector; using VVVVI = vector; using VL = vector; using VVL = vector; using VVVL = vector; using VVVVL = vector; using VP = vector

; using VVP = vector>; using VS = vector; using VC = vector; using VVC = vector>; using VD = vector; using VVD = vector>; using VVVD = vector; using I_I = pair; const int INF = (int)1e9 + 10; // int max > 2*10^9 const long long INFL = (ll)2e18 + 10; // ll max > 9*10^18 const int JU_5 = 100000; const int JU_6 = 1000000; const ll JU_9 = 1000000000; const ll JU_18 = JU_9*JU_9; #define YES cout << "YES" << endl #define NO cout << "NO" << endl #define Yes cout << "Yes" << endl #define No cout << "No" << endl template pair operator+(const pair &a, const pair &b) { return make_pair(a.first + b.first, a.second + b.second); } template pair operator-(const pair &a, const pair &b) { return make_pair(a.first - b.first, a.second - b.second); } template pair operator*(const pair &a, const pair &b) { return make_pair(a.first * b.first, a.second * b.second); } template pair operator/(const pair &a, const pair &b) { return make_pair(a.first / b.first, a.second / b.second); } // #define MOD 1000000007 #define MOD 998244353 #define pmod(x,y) ((x%y)+y)%y /********** libs **********/ //@formatter:off // jhelper 用変数 ostream *__cout; istream *__cin; void _init_io(std::istream &cin, std::ostream &cout) { // 入出力高速化用 ios::sync_with_stdio(false); cin.tie(nullptr); cout << std::setprecision(30); // jhelper 用 __cout = &cout; __cin = &cin; } //@formatter:off /* デバッグ用 出力 */ template ostream &operator<<(ostream &os, const deque &vec) { os << "deq["; for (auto v: vec) os << v << ","; os << "]"; return os; } template ostream &operator<<(ostream &os, const set &vec) { os << "{"; for (auto v: vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_set &vec) { os << "{"; for (auto v: vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const multiset &vec) { os << "{"; for (auto v: vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_multiset &vec) { os << "{"; for (auto v: vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const pair &pa) { os << "(" << pa.first << "," << pa.second << ")"; return os; } template ostream &operator<<(ostream &os, const map &mp) { os << "{"; for (auto v: mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_map &mp) { os << "{"; for (auto v: mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } // print like python // src: https://qiita.com/Lily0727K/items/06cb1d6da8a436369eed ///////////////////////////////////////////////////////// void print() { *__cout << '\n'; } template void print(Head &&head, Tail &&... tail) { *__cout << head; if (sizeof...(tail) != 0) *__cout << " "; print(forward(tail)...); } template void print(vector &vec) { for (auto &a: vec) { *__cout << a; if (&a != &vec.back()) *__cout << " "; } *__cout << '\n'; } template void print(vector> &df) { for (auto &vec: df) { print(vec); } } // endl なし void Print() {} template void Print(Head &&head, Tail &&... tail) { *__cout << head; if (sizeof...(tail) != 0) *__cout << " "; Print(forward(tail)...); } template void Print(vector &vec) { for (auto &a: vec) { *__cout << a; if (&a != &vec.back()) *__cout << " "; } } //@formatter:off /* * org: https://atcoder.jp/contests/abc213/submissions/24901856 * jhelper で使用するため, 全部 cin での入力にしている. (現状のレベルでは困らないので) */ template void scan(T& a){ *__cin >> a; } template void scan(vector&); template void scan(pair&); template void scan(vector& a){ for(auto&& i : a) scan(i); } template void scan(pair& p){ scan(p.first); scan(p.second); } template void scan(T (&a)[size]){ for(auto&& i : a) scan(i); } void in(){} template void in(T&... a){ (void)initializer_list{ (scan(a), 0)... }; } #define let_v(type,name,...) vectorname(__VA_ARGS__) #define let_V(type,name,size) vectorname(size);in(name) #define let_vv(type,name,h,...) vector>name(h,vector(__VA_ARGS__)) #define let_VV(type,name,h,w) vector>name(h,vector(w));in(name) #define let_vvv(type,name,h,w,...) vector>>name(h,vector>(w,vector(__VA_ARGS__))) #define let_vvvv(type,name,h,w,x,...) vector>>>name(h,vector>>(w,vector>(x,vector(__VA_ARGS__)))) /* string 入力を vector で受け取るみたいな */ vector let_CharVec() { string s; *__cin >> s; return {s.begin(), s.end()}; } //@formatter:off //ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } ll lcm(ll a, ll b) { return a / gcd(a, b) * b; } template bool chmax(T& a, C b) { if (a < b) { a = b; return true; } return false; } template bool chmin(T& a, C b) { if (a > b) { a = b; return true; } return false; } template T sum(const vector& v) { T res = 0; for (size_t i = 0; i < v.size(); ++i) res += v[i]; return res; } //template //T min(T a, C b) { return a <= b ? a : T(b); } // //template //T max(T a, C b) { return a >= b ? a : T(b); } template vector> idx_pair(vector &vals) { vector> ans; rep(i, vals.size()) { ans.emplace_back(vals[i], i); } return ans; } template int argmax(vector &vals){ if(vals.size()==0)return -1; int res=0; for(int i = 1;ivals[res])res=i; } return res; } template int argmin(vector &vals){ if(vals.size()==0)return -1; int res=0; for(int i = 1;i data; UnionFind(int size) : data(size, -1) {} // マージする. すでに同じ集合なら false を返す bool merge(int x, int y) { x = root(x); y = root(y); if (x == y) return false; if (data[y] < data[x]) swap(x, y); data[x] += data[y]; data[y] = x; return true; } // alias merge bool unite(int x, int y) { return merge(x, y); } int root(int x) { return data[x] < 0 ? x : (data[x] = root(data[x])); } vector root_ids() { vector res; for (int i = 0; i < data.size(); i++) { if (data[i] < 0) res.push_back(i); } return res; } // グループの要素数 int size(int x) { return -data[root(x)]; } bool issame(int x, int y) { return root(x) == root(y); } }; // #include "../library/tree/SegmentTree.cpp" // #include "../library/others/Zaatsu.cpp" /** * https://ei1333.github.io/luzhiled/snippets/graph/template.html * グラフのテンプレート */ template struct edge { int src, to; T cost; int edge_idx; edge(int to, T cost) : src(-1), to(to), cost(cost) {} edge(int src, int to, T cost) : src(src), to(to), cost(cost) {} edge &operator=(const int &x) { to = x; return *this; } operator int() const { return to; } }; template using Edges = vector >; template using WeightedGraph = vector >; using UnWeightedGraph = vector >; template using Matrix = vector >; vector> _we; template WeightedGraph read_weighted_graph(int n, int m, bool directed = false) { WeightedGraph g(n); Edges edges; for (int i = 0; i < m; ++i) { int a, b; T v; *__cin >> a >> b >> v; a--, b--; edge e(a, b, v); e.edge_idx = i; edges.push_back(e); g[a].push_back(e); if (!directed) { edge rev(b, a, v); rev.edge_idx = i; g[b].push_back(rev); } } // _we=edges; return g; }; vector>_unwaited_edges; inline UnWeightedGraph read_unwaited_graph(int n, int m, bool directed = false) { UnWeightedGraph g(n); _unwaited_edges.clear(); for (int i = 0; i < m; ++i) { int a, b; *__cin >> a >> b; a--, b--; g[a].push_back(b); if (!directed)g[b].push_back(a); _unwaited_edges.push_back({a, b}); } return g; } vector> _weighted_edges; inline WeightedGraph read_1wait_graph(int n, int m, bool directed = false) { WeightedGraph g(n); _weighted_edges.clear(); for (int i = 0; i < m; ++i) { int a, b; *__cin >> a >> b; a--, b--; edge e(a, b, 1ll); e.edge_idx = i; _weighted_edges.push_back(e); g[a].push_back(e); if (!directed) { edge rev(b, a, 1ll); rev.edge_idx = i; g[b].push_back(rev); } } return g; } WeightedGraph cnv_waited_graph(VVI &g){ WeightedGraph res(g.size()); rep(u,g.size()){ for(auto v:g[u]){ res[u].push_back({u,v,1}); } } return res; } /** * weighted graph 上に st からの path が存在するか調べる * @param g weghted graph * @param st * @param reverse 辺を逆向きにする場合は true に * @return path の存在を {0, 1} のフラグ値で表す vector */ template vector has_path_on_wg(WeightedGraph &g, int st, bool reverse = false) { int n = g.size(); vector> g2(n); rep(i, n) { for (auto j: g[i]) { if (j != i) { if (reverse) g2[j].push_back(i); else g2[i].push_back(j); } } } vector res(g.size(), 0); res[st] = 1; queue que; que.push(st); while (!que.empty()) { int u = que.front(); que.pop(); for (auto e: g2[u]) { if (res[e])continue; res[e] = 1; que.push(e); } } return res; } // utils // #include "../library/mint.cpp" // #include "../library/string/utils.cpp" // #include "../library/math/utils.cpp" /**************************/ class yuki { public: void solve(std::istream &cin, std::ostream &cout) { _init_io(cin, cout); int t = 1; // cin >> t; while (t--) _solve(cin, cout); } //@formatter:on void _solve(std::istream &cin, std::ostream &cout) { // code int n,m; cin >> n >> m; VL in(n,0); VL out(n,0); UnionFind uf(n); rep(i,m){ int a,b;cin>> a>> b; a--,b--; in[b]++; out[a]++; } ll totout=0; ll totin=0; bool inltout=false; bool outltin=false; rep(i,n) { if(in[i]>out[i]){ if(!inltout){ totin+=(in[i]-1)-out[i]; }else{ totin+=in[i]-out[i]; } inltout=true; } if(in[i]