#line 1 ".lib/template.hpp" #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define allof(obj) (obj).begin(), (obj).end() #define range(i, l, r) for(int i=l;i>1)|y_bit)) #define bit_kth(i, k) ((i >> k)&1) #define bit_highest(i) (i?63-__builtin_clzll(i):-1) #define bit_lowest(i) (i?__builtin_ctzll(i):-1) #define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t)) using ll = long long; using ld = long double; using ul = uint64_t; using pi = std::pair; using pl = std::pair; using namespace std; template std::ostream &operator<<(std::ostream &dest, const std::pair &p){ dest << p.first << ' ' << p.second; return dest; } template std::ostream &operator<<(std::ostream &dest, const std::vector> &v){ int sz = v.size(); if(sz==0) return dest; for(int i=0;i std::ostream &operator<<(std::ostream &dest, const std::vector &v){ int sz = v.size(); if(sz==0) return dest; for(int i=0;i std::ostream &operator<<(std::ostream &dest, const std::array &v){ if(sz==0) return dest; for(int i=0;i std::ostream &operator<<(std::ostream &dest, const std::set &v){ for(auto itr=v.begin();itr!=v.end();){ dest << *itr; itr++; if(itr!=v.end()) dest << ' '; } return dest; } template std::ostream &operator<<(std::ostream &dest, const std::map &v){ for(auto itr=v.begin();itr!=v.end();){ dest << '(' << itr->first << ", " << itr->second << ')'; itr++; if(itr!=v.end()) dest << '\n'; } return dest; } template vector make_vec(size_t sz, T val){return std::vector(sz, val);} template auto make_vec(size_t sz, Tail ...tail){ return std::vector(tail...))>(sz, make_vec(tail...)); } template vector read_vec(size_t sz){ std::vector v(sz); for(int i=0;i<(int)sz;i++) std::cin >> v[i]; return v; } template auto read_vec(size_t sz, Tail ...tail){ auto v = std::vector(tail...))>(sz); for(int i=0;i<(int)sz;i++) v[i] = read_vec(tail...); return v; } void io_init(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); } #line 1 ".lib/graph/graph.hpp" #line 1 ".lib/graph/edge.hpp" /* template struct edge_base{ using weight = edge_weight; int to(); int from(); int id(); weight wei(); static weight z(); edge_base reverse(); }; */ template struct simple_edge{ using weight = edge_weight; int s, t; simple_edge(): s(-1), t(-1){} simple_edge(int a, int b): s(a), t(b){} int to(){return t;} int from(){return s;} int id(){return -1;} weight wei(){return 1;} static weight z(){return 0;} simple_edge reverse(){return simple_edge{t, s};} }; template struct weighted_edge{ using weight = edge_weight; int s, t; weight w; weighted_edge(): s(-1), t(-1), w(0){} weighted_edge(int a, int b, weight c): s(a), t(b), w(c){} int to(){return t;} int from(){return s;} int id(){return -1;} weight wei(){return w;} static weight z(){return 0;} weighted_edge reverse(){return weighted_edge{t, s, w};} }; template struct labeled_edge{ using weight = edge_weight; int s, t, i; labeled_edge(): s(-1), t(-1), i(-1){} labeled_edge(int a, int b, int i): s(a), t(b), i(i){} int to(){return t;} int from(){return s;} int id(){return i;} weight wei(){return 1;} static weight z(){return 0;} labeled_edge reverse(){return labeled_edge{t, s, i};} }; template struct weighted_labeled_edge{ using weight = edge_weight; int s, t; weight w; int i; weighted_labeled_edge(): s(-1), t(-1), w(0), i(-1){} weighted_labeled_edge(int a, int b, weight w, int i): s(a), t(b), w(w), i(i){} int to(){return t;} int from(){return s;} int id(){return i;} weight wei(){return w;} static weight z(){return 0;} weighted_labeled_edge reverse(){return weighted_labeled_edge{t, s, w, i};} }; #line 1 ".lib/graph/graph_algorithm.hpp" #line 7 ".lib/graph/graph_algorithm.hpp" #include #line 9 ".lib/graph/graph_algorithm.hpp" namespace graph_algorithm{ template using vec = std::vector; // O(V + E) // 辺の重みが1 template struct bfs_shortest_path{ private: using weight = typename edge::weight; using dist_p = std::pair; vec> &g; public: bfs_shortest_path(vec> &g): g(g){} static constexpr weight inf = std::numeric_limits::max() / 2; static constexpr weight minf = std::numeric_limits::min() / 2; vec dist; vec par; void build(int s){ int n = g.size(); if(dist.empty()){ dist.resize(n, inf); par.resize(n, edge{}); }else{ std::fill(dist.begin(), dist.end(), inf); std::fill(par.begin(), par.end(), edge{}); } std::queue que; dist[s] = edge::z(); que.push(dist_p(edge::z(), s)); while(!que.empty()){ auto [w, v] = que.front(); que.pop(); if(dist[v] < w) continue; for(edge &e: g[v]){ assert(e.wei() == 1); weight d = dist[v] + e.wei(); int to = e.to(); if(dist[to] > d){ dist[to] = d; par[to] = e; que.push(dist_p(d, to)); } } } } vec get_path(int v){ assert(!dist.empty()); vec ret; while(par[v].from() != -1) ret.push_back(par[v]), v = par[v].from(); std::reverse(ret.begin(), ret.end()); return ret; } weight operator [](int v){return dist[v];} }; // O(V + E) // 辺の重みが0か1 template struct zero_one_bfs_shortest_path{ private: using weight = typename edge::weight; vec> &g; public: zero_one_bfs_shortest_path(vec> &g): g(g){} static constexpr weight inf = std::numeric_limits::max() / 2; static constexpr weight minf = std::numeric_limits::min() / 2; vec dist; vec par; void build(int s){ int n = g.size(); if(dist.empty()){ dist.resize(n, inf); par.resize(n, edge{}); }else{ std::fill(dist.begin(), dist.end(), inf); std::fill(par.begin(), par.end(), edge{}); } std::queue que0, que1; dist[s] = edge::z(); weight dcur = dist[s]; que0.push(s); while(!que0.empty() || !que1.empty()){ if(que0.empty()){ std::swap(que0, que1); dcur++; } int v = que0.front(); que0.pop(); if(dist[v] < dcur) continue; for(edge &e: g[v]){ weight w = e.wei(); assert(w == 0 || w == 1); weight d = dist[v] + w; if(dist[e.t] > d){ dist[e.t] = d; par[e.t] = e; if(w == 0) que0.push(e.t); else que1.push(e.t); } } } } vec get_path(int v){ assert(!dist.empty()); vec ret; while(par[v].from() != -1) ret.push_back(par[v]), v = par[v].from(); std::reverse(ret.begin(), ret.end()); return ret; } weight operator [](int v){return dist[v];} }; // O((V + E)logV) // 辺の重みが非負(負の閉路がなければ一応動く) template struct dijkstra{ private: using weight = typename edge::weight; using dist_p = std::pair; vec> &g; public: dijkstra(vec> &g): g(g){} static constexpr weight inf = std::numeric_limits::max() / 2; static constexpr weight minf = std::numeric_limits::min() / 2; vec dist; vec par; void build(int s){ int n = g.size(); if(dist.empty()){ dist.resize(n, inf); par.resize(n, edge{}); }else{ std::fill(dist.begin(), dist.end(), inf); std::fill(par.begin(), par.end(), edge{}); } std::priority_queue, std::greater> que; dist[s] = edge::z(); que.push(dist_p(edge::z(), s)); while(!que.empty()){ auto [w, v] = que.top(); que.pop(); if(dist[v] < w) continue; for(edge &e: g[v]){ weight d = dist[v] + e.wei(); int to = e.to(); if(dist[to] > d){ dist[to] = d; par[to] = e; que.push(dist_p(d, to)); } } } } vec get_path(int v){ assert(!dist.empty()); vec ret; while(par[v].from() != -1) ret.push_back(par[v]), v = par[v].from(); std::reverse(ret.begin(), ret.end()); return ret; } weight operator [](int v){return dist[v];} }; // O(VE) // inf: 到達不可, minf: 負の閉路 template struct bellman_ford{ private: using weight = typename edge::weight; using dist_p = std::pair; vec> &g; public: bellman_ford(vec> &g): g(g){} static constexpr weight inf = std::numeric_limits::max() / 2; static constexpr weight minf = std::numeric_limits::min() / 2; vec dist; vec par; void build(int s){ int n = g.size(); if(dist.empty()){ dist.resize(n, inf); par.resize(n); }else{ std::fill(dist.begin(), dist.end(), inf); std::fill(par.begin(), par.end(), edge{}); } dist[s] = edge::z(); for(int lp = 0; ; lp++){ bool update = false; for(int i = 0; i < n; i++){ if(dist[i] == inf) continue; for(edge e : g[i]){ weight &dto = dist[e.to()]; if(dto == minf){ if(dto != minf) update = true; dto = minf; }else if(dto == inf || dto > dist[i] + e.wei()){ dto = (lp > n ? minf : dist[i] + e.wei()); par[e.to()] = e; update = true; } } } if(!update) break; } } vec get_path(int v){ assert(!dist.empty()); vec ret; while(par[v].from() != -1) ret.push_back(par[v]), v = par[v].from(); std::reverse(ret.begin(), ret.end()); return ret; } weight operator [](int v){return dist[v];} }; // O(V^3) template struct warshall_floyd{ private: using weight = typename edge::weight; vec> &g; public: warshall_floyd(vec> &g): g(g){} static constexpr weight inf = std::numeric_limits::max() / 2; static constexpr weight minf = std::numeric_limits::min() / 2; vec> dist; void build(){ int n = g.size(); dist.resize(n, vec(n, inf)); for(int i = 0; i < n; i++){ dist[i][i] = 0; for(edge &e : g[i]){ dist[i][e.to()] = std::min(dist[i][e.to()], e.wei()); } } for(int k = 0; k < n; k++){ for(int s = 0; s < n; s++){ for(int t = 0; t < n; t++){ dist[s][t] = std::min(dist[s][t], dist[s][k] + dist[k][t]); } } } } vec& operator [](int v){return dist[v];} }; }; namespace graph_algorithm{ // {連結成分, DAG} template std::pair, vec>> scc(vec> &g){ int n = g.size(); vec v(n), cmp(n, 0); vec> rg(n), V; auto scc_dfs = [&](auto &&scc_dfs, int cur, int &sz)->void{ cmp[cur] = -1; for(edge &e : g[cur]){ int to = e.to(); rg[to].push_back(cur); if(cmp[to] == 0) scc_dfs(scc_dfs, to, sz); } v[sz++] = cur; }; auto scc_rdfs = [&](auto &&scc_rdfs, int cur, const int k)->void{ cmp[cur] = k; V[k].push_back(cur); for(int to : rg[cur]) if(cmp[to] == -1) scc_rdfs(scc_rdfs, to, k); }; for(int i = 0, j = 0; i < n; i++) if(!cmp[i]) scc_dfs(scc_dfs, i, j); for(int i = (int)v.size() - 1, j = 0; i >= 0; i--){ if(cmp[v[i]] == -1){ V.push_back(vec()); scc_rdfs(scc_rdfs, v[i], j++); } } return {cmp, V}; } // {連結成分, 森} template std::pair, vec>> two_edge_connected(vec> &g){ int n = g.size(); vec v(n), cmp(n, 0); vec> V; vec> edge_used(n); auto tec_dfs = [&](auto &&tec_dfs, int cur, int &sz)->void{ cmp[cur] = -1; for(int i = 0; i < g[cur].size(); i++){ int to = g[cur][i].to(); if(cmp[to] == 0) edge_used[cur][i] = true, tec_dfs(tec_dfs, to, sz); } v[sz++] = cur; }; auto tec_rdfs = [&](auto &&tec_rdfs, int cur, const int k)->void{ cmp[cur] = k; V[k].push_back(cur); for(int i = 0; i < g[cur].size(); i++){ int to = g[cur][i].to(); if(cmp[to] == -1 && !edge_used[cur][i]) tec_rdfs(tec_rdfs, to, k); } }; for(int i = 0; i < n; i++) edge_used[i].resize(g[i].size(), 0); for(int i = 0, j = 0; i < n; i++) if(!cmp[i]) tec_dfs(tec_dfs, i, j); for(int i = (int)v.size() - 1, j = 0; i >= 0; i--){ if(cmp[v[i]] == -1){ V.push_back(vec()); tec_rdfs(tec_rdfs, v[i], j++); } } return {cmp, V}; } // 二重頂点連結成分分解 // {間接点フラグ, 各連結成分が含む頂点} template std::pair, vec>> bcc(vec> &g){ int n = g.size(); vec> V; vec child(n, 0), dep(n, -1), low(n); vec used(n, false), is_articulation(n, false); vec tmp_edge; auto bcc_dfs = [&](auto &&bcc_dfs, int cur, int par, int d)->void{ if(par != -1) child[par]++; dep[cur] = low[cur] = d; for(edge &e : g[cur]){ int to = e.to(); if(to == par) continue; if(dep[to] < dep[cur]) tmp_edge.push_back(e); if(dep[e.to()] == -1){ bcc_dfs(bcc_dfs, to, cur, d + 1); if(low[to] >= dep[cur]){ is_articulation[cur] = true; V.push_back(vec()); bool is_ok = false; while(!tmp_edge.empty() && !is_ok){ edge e = tmp_edge.back(); tmp_edge.pop_back(); if(e.from() == cur && e.to() == to) is_ok = true; if(!used[e.to()]) V.back().push_back(e.to()), used[e.to()] = true; if(!used[e.from()]) V.back().push_back(e.from()), used[e.from()] = true; } for(int v : V.back()) used[v] = false; } low[cur] = std::min(low[cur], low[to]); }else low[cur] = std::min(low[cur], dep[to]); } }; for(int i = 0; i < n; i++){ if(dep[i] != -1) continue; int vsz_pre = V.size(); bcc_dfs(bcc_dfs, i, -1, 0); is_articulation[i] = (child[i] > 1); if(V.size() == vsz_pre) V.push_back(vec{i});// 孤立点 } return {is_articulation, V}; } template std::tuple, vec, vec>>> block_cut_tree(vec> &g){ auto [is_articulation, V] = bcc(g); int n = g.size(); vec cmp(n, -1); int m = V.size(), a = m; for(int i = 0; i < m; i++){ for(int v : V[i]){ if(is_articulation[v]) cmp[v] = a++; else cmp[v] = i; } } vec>> G(a); for(int i = 0; i < m; i++){ for(int v : V[i]){ if(is_articulation[v]){ G[i].push_back({i, cmp[v]}); G[cmp[v]].push_back({cmp[v], i}); } } } return {is_articulation, cmp, G}; } }; namespace graph_algorithm{ // 終了時にinが0でない要素がある -> 閉路が存在する // 閉路があるなら空のvectorを返す template vec topological_sort(vec> &g){ int n = g.size(); std::queue que; vec in(n, 0), ret; for(int i = 0; i < n; i++) for(edge e : g[i]) in[e.to()]++; for(int i = 0; i < n; i++) if(!in[i]) que.push(i); while(!que.empty()){ int p = que.front(); que.pop(); ret.push_back(p); for(edge &e : g[p]){ int to = e.to(); if(!(--in[to])) que.push(to); } } for(int i = 0; i < n; i++) if(in[i] != 0) return {}; return ret; } // プリム法, 連結なら始点sは関係ない template vec undirected_mst(vec> &g, int s = 0){ int n = g.size(); assert(s < n); static vec V(n, 0); vec ret; using pde = std::pair; std::priority_queue, std::function> que([](pde a, pde b){ return a.first > b.first; }); V[s] = true; for(edge &e : g[s]) que.push(pde{e.wei(), e}); while(!que.empty()){ auto [d, e] = que.top(); que.pop(); if(V[e.to()]) continue; V[e.to()] = true; ret.push_back(e); for(edge &ec : g[e.to()]) if(!V[ec.to()]) que.push({ec.wei(), ec}); } for(edge &e : ret) V[e.to()] = V[e.from()] = false; return ret; } // rを根とするbfs木O(V + E) template vec> bfs_tree(vec> &g, int r){ int n = g.size(); std::queue que; vec used(n, false); que.push(r); vec> ret(n); used[r] = true; while(!que.empty()){ int v = que.front(); que.pop(); for(edge &e : g[v]){ int to = e.to(); if(used[to]) continue; used[to] = true; ret[v].push_back(e); que.push(to); } } return ret; } // rを根とするbfs木, 最短経路的 O((V + E)logV) // {木, 重みのテーブル} template std::pair>, vec> bfs_tree_shortest(vec> &g, int r){ int n = g.size(); using weight = typename edge::weight; using pdv = std::pair; static constexpr weight inf = std::numeric_limits::max() / 2; std::priority_queue, std::greater> que; vec dist(n, inf); dist[r] = edge::z(); que.push({edge::z(), r}); vec> pedge(n); vec> ret(n); while(!que.empty()){ auto [d, v] = que.top(); que.pop(); if(dist[v] < d) continue; for(edge &e : g[v]){ int to = e.to(); weight nxtd = d + e.wei(); if(dist[to] > nxtd){ dist[to] = nxtd; if(!pedge[to].empty()) pedge[to].pop_back(); pedge[to].push_back(e); que.push({nxtd, to}); } } } for(int i = 0; i < n; i++){ if(!pedge[i].empty()){ edge e = pedge[i][0]; ret[e.s].push_back(e); } } return {ret, dist}; } // g[i]の辺を{同じcmpへの辺, 異なるcmpへの辺}に並び替える, O(V + E) template void cmp_edge_arrange(const vec &cmp, vec> &g){ int n = g.size(); for(int i = 0; i < n; i++){ int m = g[i].size(); int l = 0, r = m - 1; while(l < r){ while(l < m && cmp[i] == cmp[g[i][l].to()]) l++; while(0 < r && cmp[i] == cmp[g[i][r].to()]) r--; if(l < r) std::swap(g[i][l], g[i][r]); } } } }; #line 7 ".lib/graph/graph.hpp" template struct general_graph{ using weight = typename edge::weight; template using vec = std::vector; using graph = vec>; using simple_graph = general_graph>; int n; graph g; general_graph(int n): n(n), g(n){} general_graph(const vec> &G): n(G.size()), g(G){} void add_edge(int a, edge e){ g[a].push_back(e); } graph_algorithm::bfs_shortest_path bfs_shortest_path(){ return graph_algorithm::bfs_shortest_path(g); } graph_algorithm::zero_one_bfs_shortest_path zero_one_bfs_shortest_path(){ return graph_algorithm::zero_one_bfs_shortest_path(g); } graph_algorithm::dijkstra dijkstra(){ return graph_algorithm::dijkstra(g); } graph_algorithm::bellman_ford bellman_ford(){ return graph_algorithm::bellman_ford(g); } graph_algorithm::warshall_floyd warshall_floyd(){ return graph_algorithm::warshall_floyd(g); } static simple_graph make_simple_graph(const vec> &G){ int n = G.size(); vec>> G2(n); for(int i = 0; i < n; i++) for(int j : G[i]) G2[i].push_back(simple_edge(i, j)); return simple_graph(G2); } // {連結成分, グラフ} 有向サイクル std::pair, simple_graph> scc(){ vec cmp = graph_algorithm::scc(g).first; int m = *std::max_element(cmp.begin(), cmp.end()); vec> G(m); for(int i = 0; i < n; i++){ for(auto &e : g[i]){ if(cmp[i] != cmp[e.t]){ G[cmp[i]].push_back(cmp[e.t]); } } } for(int i = 0; i < m; i++){ std::sort(G[i].begin(), G[i].end()); G[i].erase(std::unique(G[i].begin(), G[i].end()), G[i].end()); } return {cmp, make_simple_graph(G)}; } // {連結成分, グラフ} 1つの辺が消えても連結, 森か木になる std::pair, vec>> two_edge_connected(){ vec cmp = graph_algorithm::scc(g).first; int m = *std::max_element(cmp.begin(), cmp.end()); vec> G(m); for(int i = 0; i < n; i++){ for(auto &e : g[i]){ if(cmp[i] != cmp[e.t]){ G[cmp[i]].push_back(cmp[e.t]); } } } return {cmp, G}; } // {関節点フラグ, 各連結成分が含む頂点(関節点は複数の連結成分に含まれる))} 1つの頂点が消えても連結 std::pair, vec>> bcc(){ return graph_algorithm::bcc(g); } // {関節点フラグ, cmp, 森} 1つの頂点が消えても連結, 森か木になる std::tuple, vec, vec>> block_cut_tree(){ return graph_algorithm::block_cut_tree(g); } // 閉路が存在するなら空のvector vec topological_sort(){ return graph_algorithm::topological_sort(g); } // 最小全域木, グラフが連結ならsの値は関係ない vec undirected_mst(int s = 0){ return graph_algorithm::undirected_mst(g, s); } // rを根とするbfs木O(V + E) vec> bfs_tree(int r){ return graph_algorithm::bfs_tree(g, r); } // rを根とするbfs木, rからの最短経路 O((V + E)logV) std::pair>, vec> bfs_tree_shortest(int r){ return graph_algorithm::bfs_tree_shortest(g, r); } // g[i]の辺を{同じcmpへの辺, 異なるcmpへの辺}に並び替える, O(V + E) void cmp_edge_arrange(const vec &cmp){ graph_algorithm::cmp_edge_arrange(cmp, g); } vec &operator [](int i){return g[i];} }; using simple_graph = general_graph>; template using weighted_graph = general_graph>; template using labeled_graph = general_graph>; template using weighted_labeled_graph = general_graph>; #line 3 "a.cpp" int main(){ io_init(); // d[x] := 出次数 - 入次数 int n, m; std::cin >> n >> m; using edge = weighted_labeled_edge; general_graph g(n); range(i, 0, m){ int a, b; std::cin >> a >> b; a--, b--; g.add_edge(a, {a, b, 1, i}); } vector pos(n, 0); vector E; vector use(n, false); auto f = [&](auto &&f, int cur)->void{ if(use[cur]){ while(true){ edge *e = E.back(); E.pop_back(); e->w = 0; use[e->s] = false; if(e->s == cur) break; } } for(; pos[cur] < g[cur].size();){ use[cur] = 1; int to = g[cur][pos[cur]].t; int id = g[cur][pos[cur]].i; E.push_back(&g[cur][pos[cur]]); pos[cur]++; f(f, to); if(!E.empty() && E.back()->i == id) E.pop_back(); } use[cur] = 0; }; range(i, 0, n) f(f, i); vector ans; range(i, 0, n){ for(auto e : g[i]){ if(e.w == 0) continue; ans.push_back(e); } } std::cout << n << " " << ans.size() << '\n'; range(i, 0, ans.size()) std::cout << ans[i].s + 1 << " " << ans[i].t + 1 << '\n'; }