#line 1 ".lib/template.hpp" #include <iostream> #include <string> #include <vector> #include <array> #include <tuple> #include <stack> #include <queue> #include <deque> #include <algorithm> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <bitset> #include <cmath> #include <functional> #include <cassert> #include <climits> #include <iomanip> #include <numeric> #include <memory> #include <random> #include <thread> #include <chrono> #define allof(obj) (obj).begin(), (obj).end() #define range(i, l, r) for(int i=l;i<r;i++) #define unique_elem(obj) obj.erase(std::unique(allof(obj)), obj.end()) #define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S) #define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>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<int, int>; using pl = std::pair<ll, ll>; using namespace std; template<typename F, typename S> std::ostream &operator<<(std::ostream &dest, const std::pair<F, S> &p){ dest << p.first << ' ' << p.second; return dest; } template<typename T> std::ostream &operator<<(std::ostream &dest, const std::vector<std::vector<T>> &v){ int sz = v.size(); if(sz==0) return dest; for(int i=0;i<sz;i++){ int m = v[i].size(); for(int j=0;j<m;j++) dest << v[i][j] << (i!=sz-1&&j==m-1?'\n':' '); } return dest; } template<typename T> std::ostream &operator<<(std::ostream &dest, const std::vector<T> &v){ int sz = v.size(); if(sz==0) return dest; for(int i=0;i<sz-1;i++) dest << v[i] << ' '; dest << v[sz-1]; return dest; } template<typename T, size_t sz> std::ostream &operator<<(std::ostream &dest, const std::array<T, sz> &v){ if(sz==0) return dest; for(int i=0;i<sz-1;i++) dest << v[i] << ' '; dest << v[sz-1]; return dest; } template<typename T> std::ostream &operator<<(std::ostream &dest, const std::set<T> &v){ for(auto itr=v.begin();itr!=v.end();){ dest << *itr; itr++; if(itr!=v.end()) dest << ' '; } return dest; } template<typename T, typename E> std::ostream &operator<<(std::ostream &dest, const std::map<T, E> &v){ for(auto itr=v.begin();itr!=v.end();){ dest << '(' << itr->first << ", " << itr->second << ')'; itr++; if(itr!=v.end()) dest << '\n'; } return dest; } template<typename T> vector<T> make_vec(size_t sz, T val){return std::vector<T>(sz, val);} template<typename T, typename... Tail> auto make_vec(size_t sz, Tail ...tail){ return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...)); } template<typename T> vector<T> read_vec(size_t sz){ std::vector<T> v(sz); for(int i=0;i<(int)sz;i++) std::cin >> v[i]; return v; } template<typename T, typename... Tail> auto read_vec(size_t sz, Tail ...tail){ auto v = std::vector<decltype(read_vec<T>(tail...))>(sz); for(int i=0;i<(int)sz;i++) v[i] = read_vec<T>(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<typename edge_weight> struct edge_base{ using weight = edge_weight; int to(); int from(); int id(); weight wei(); static weight z(); edge_base<weight> reverse(); }; */ template<typename edge_weight> 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<weight> reverse(){return simple_edge<weight>{t, s};} }; template<typename edge_weight> 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<weight> reverse(){return weighted_edge<weight>{t, s, w};} }; template<typename edge_weight> 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<weight> reverse(){return labeled_edge<weight>{t, s, i};} }; template<typename edge_weight> 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<weight> reverse(){return weighted_labeled_edge<weight>{t, s, w, i};} }; #line 1 ".lib/graph/graph_algorithm.hpp" #line 7 ".lib/graph/graph_algorithm.hpp" #include <limits> #line 9 ".lib/graph/graph_algorithm.hpp" namespace graph_algorithm{ template<typename T> using vec = std::vector<T>; // O(V + E) // 辺の重みが1 template<typename edge> struct bfs_shortest_path{ private: using weight = typename edge::weight; using dist_p = std::pair<weight, int>; vec<vec<edge>> &g; public: bfs_shortest_path(vec<vec<edge>> &g): g(g){} static constexpr weight inf = std::numeric_limits<weight>::max() / 2; static constexpr weight minf = std::numeric_limits<weight>::min() / 2; vec<weight> dist; vec<edge> 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<dist_p> 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<edge> get_path(int v){ assert(!dist.empty()); vec<edge> 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<typename edge> struct zero_one_bfs_shortest_path{ private: using weight = typename edge::weight; vec<vec<edge>> &g; public: zero_one_bfs_shortest_path(vec<vec<edge>> &g): g(g){} static constexpr weight inf = std::numeric_limits<weight>::max() / 2; static constexpr weight minf = std::numeric_limits<weight>::min() / 2; vec<weight> dist; vec<edge> 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<int> 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<edge> get_path(int v){ assert(!dist.empty()); vec<edge> 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<typename edge> struct dijkstra{ private: using weight = typename edge::weight; using dist_p = std::pair<weight, int>; vec<vec<edge>> &g; public: dijkstra(vec<vec<edge>> &g): g(g){} static constexpr weight inf = std::numeric_limits<weight>::max() / 2; static constexpr weight minf = std::numeric_limits<weight>::min() / 2; vec<weight> dist; vec<edge> 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<dist_p, vec<dist_p>, std::greater<dist_p>> 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<edge> get_path(int v){ assert(!dist.empty()); vec<edge> 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<typename edge> struct bellman_ford{ private: using weight = typename edge::weight; using dist_p = std::pair<weight, int>; vec<vec<edge>> &g; public: bellman_ford(vec<vec<edge>> &g): g(g){} static constexpr weight inf = std::numeric_limits<weight>::max() / 2; static constexpr weight minf = std::numeric_limits<weight>::min() / 2; vec<weight> dist; vec<edge> 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<edge> get_path(int v){ assert(!dist.empty()); vec<edge> 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<typename edge> struct warshall_floyd{ private: using weight = typename edge::weight; vec<vec<edge>> &g; public: warshall_floyd(vec<vec<edge>> &g): g(g){} static constexpr weight inf = std::numeric_limits<weight>::max() / 2; static constexpr weight minf = std::numeric_limits<weight>::min() / 2; vec<vec<weight>> dist; void build(){ int n = g.size(); dist.resize(n, vec<weight>(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<weight>& operator [](int v){return dist[v];} }; }; namespace graph_algorithm{ // {連結成分, DAG} template<typename edge> std::pair<vec<int>, vec<vec<int>>> scc(vec<vec<edge>> &g){ int n = g.size(); vec<int> v(n), cmp(n, 0); vec<vec<int>> 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<int>()); scc_rdfs(scc_rdfs, v[i], j++); } } return {cmp, V}; } // {連結成分, 森} template<typename edge> std::pair<vec<int>, vec<vec<int>>> two_edge_connected(vec<vec<edge>> &g){ int n = g.size(); vec<int> v(n), cmp(n, 0); vec<vec<int>> V; vec<vec<bool>> 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<int>()); tec_rdfs(tec_rdfs, v[i], j++); } } return {cmp, V}; } // 二重頂点連結成分分解 // {間接点フラグ, 各連結成分が含む頂点} template<typename edge> std::pair<vec<bool>, vec<vec<int>>> bcc(vec<vec<edge>> &g){ int n = g.size(); vec<vec<int>> V; vec<int> child(n, 0), dep(n, -1), low(n); vec<bool> used(n, false), is_articulation(n, false); vec<edge> 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<int>()); 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<int>{i});// 孤立点 } return {is_articulation, V}; } template<typename edge> std::tuple<vec<bool>, vec<int>, vec<vec<simple_edge<int>>>> block_cut_tree(vec<vec<edge>> &g){ auto [is_articulation, V] = bcc<edge>(g); int n = g.size(); vec<int> 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<vec<simple_edge<int>>> 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<typename edge> vec<int> topological_sort(vec<vec<edge>> &g){ int n = g.size(); std::queue<int> que; vec<int> 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<typename edge> vec<edge> undirected_mst(vec<vec<edge>> &g, int s = 0){ int n = g.size(); assert(s < n); static vec<bool> V(n, 0); vec<edge> ret; using pde = std::pair<typename edge::weight, edge>; std::priority_queue<pde, vec<pde>, std::function<bool(pde, pde)>> 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<typename edge> vec<vec<edge>> bfs_tree(vec<vec<edge>> &g, int r){ int n = g.size(); std::queue<int> que; vec<bool> used(n, false); que.push(r); vec<vec<edge>> 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<typename edge> std::pair<vec<vec<edge>>, vec<typename edge::weight>> bfs_tree_shortest(vec<vec<edge>> &g, int r){ int n = g.size(); using weight = typename edge::weight; using pdv = std::pair<weight, int>; static constexpr weight inf = std::numeric_limits<weight>::max() / 2; std::priority_queue<pdv, vec<pdv>, std::greater<pdv>> que; vec<weight> dist(n, inf); dist[r] = edge::z(); que.push({edge::z(), r}); vec<vec<edge>> pedge(n); vec<vec<edge>> 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<typename edge> void cmp_edge_arrange(const vec<int> &cmp, vec<vec<edge>> &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<typename edge> struct general_graph{ using weight = typename edge::weight; template<typename T> using vec = std::vector<T>; using graph = vec<vec<edge>>; using simple_graph = general_graph<simple_edge<int>>; int n; graph g; general_graph(int n): n(n), g(n){} general_graph(const vec<vec<edge>> &G): n(G.size()), g(G){} void add_edge(int a, edge e){ g[a].push_back(e); } graph_algorithm::bfs_shortest_path<edge> bfs_shortest_path(){ return graph_algorithm::bfs_shortest_path<edge>(g); } graph_algorithm::zero_one_bfs_shortest_path<edge> zero_one_bfs_shortest_path(){ return graph_algorithm::zero_one_bfs_shortest_path<edge>(g); } graph_algorithm::dijkstra<edge> dijkstra(){ return graph_algorithm::dijkstra<edge>(g); } graph_algorithm::bellman_ford<edge> bellman_ford(){ return graph_algorithm::bellman_ford<edge>(g); } graph_algorithm::warshall_floyd<edge> warshall_floyd(){ return graph_algorithm::warshall_floyd<edge>(g); } static simple_graph make_simple_graph(const vec<vec<int>> &G){ int n = G.size(); vec<vec<simple_edge<int>>> G2(n); for(int i = 0; i < n; i++) for(int j : G[i]) G2[i].push_back(simple_edge<int>(i, j)); return simple_graph(G2); } // {連結成分, グラフ} 有向サイクル std::pair<vec<int>, simple_graph> scc(){ vec<int> cmp = graph_algorithm::scc(g).first; int m = *std::max_element(cmp.begin(), cmp.end()); vec<vec<int>> 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<int>, vec<vec<edge>>> two_edge_connected(){ vec<int> cmp = graph_algorithm::scc(g).first; int m = *std::max_element(cmp.begin(), cmp.end()); vec<vec<int>> 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<bool>, vec<vec<int>>> bcc(){ return graph_algorithm::bcc<edge>(g); } // {関節点フラグ, cmp, 森} 1つの頂点が消えても連結, 森か木になる std::tuple<vec<bool>, vec<int>, vec<vec<edge>>> block_cut_tree(){ return graph_algorithm::block_cut_tree<edge>(g); } // 閉路が存在するなら空のvector vec<int> topological_sort(){ return graph_algorithm::topological_sort(g); } // 最小全域木, グラフが連結ならsの値は関係ない vec<edge> undirected_mst(int s = 0){ return graph_algorithm::undirected_mst<edge>(g, s); } // rを根とするbfs木O(V + E) vec<vec<edge>> bfs_tree(int r){ return graph_algorithm::bfs_tree(g, r); } // rを根とするbfs木, rからの最短経路 O((V + E)logV) std::pair<vec<vec<edge>>, vec<weight>> 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<int> &cmp){ graph_algorithm::cmp_edge_arrange(cmp, g); } vec<edge> &operator [](int i){return g[i];} }; using simple_graph = general_graph<simple_edge<int>>; template<typename T> using weighted_graph = general_graph<weighted_edge<T>>; template<typename T> using labeled_graph = general_graph<labeled_edge<T>>; template<typename T> using weighted_labeled_graph = general_graph<weighted_labeled_edge<T>>; #line 1 ".lib/graph/graph_algorithm_cycle.hpp" #line 7 ".lib/graph/graph_algorithm_cycle.hpp" //#include "tree.hpp" //#include "../data_structure/segment_tree/dual_segment_tree.hpp" namespace graph_algorithm{ template<typename T> using vec = std::vector<T>; // O(V + E) // ショートカットが無い閉路を1つ返す, 閉路が無い場合は空のvector // 自己辺はサイクルと見なさない(含めたい場合, e.from = e.toの辺を探す) // 多重辺があっても良い // 無向辺の場合辺にidをつけて逆流しないようにする template<typename edge> void cycle_noshortcut(int cur, vec<vec<edge>> &g, vec<bool> &use, vec<int> &in, vec<edge> &E, vec<edge> &res, int last_edge_id){ if(in[cur] >= 0){ int s = 0; while(E[s].from() != cur) s++;// cur->curの閉路 std::queue<edge> shortcut; std::fill(use.begin(), use.end(), 0); while(res.empty()){ use[cur] = true; int skip_in = -1, end_in = -1; edge skip_e = g[cur][0], end_e = g[cur][0]; for(edge &e : g[cur]){ int to = e.to(); if(in[to] == -1 || (last_edge_id == e.id())) continue; if(in[to] > in[cur] && skip_in < in[to]) skip_in = in[to], skip_e = e; if(in[to] < in[cur] && use[to] && end_in < in[to]) end_in = in[to], end_e = e; } if(end_in != -1){ int to = end_e.to(); while(E[s].from() != to) s++; while(E.back().to() != cur) E.pop_back(); while(!shortcut.empty() && in[shortcut.front().to()] <= in[to]) shortcut.pop(); E.push_back(end_e); while(s != E.size()){ int srank = (shortcut.empty() ? g.size() : in[shortcut.front().from()]); while(s != E.size() && in[E[s].from()] < srank) res.push_back(E[s++]); if(!shortcut.empty()){ int trank = in[shortcut.front().to()]; res.push_back(shortcut.front()); shortcut.pop(); while(in[E[s].from()] < trank) s++; } } return; } if(in[cur] + 1 != skip_in) shortcut.push(skip_e); cur = skip_e.to(); last_edge_id = skip_e.id(); } return; } in[cur] = E.size(); for(edge &e : g[cur]){ if(e.to() == cur) continue; if(!use[e.to()] && res.empty() && (e.id() == -1 || e.id() != last_edge_id)){ E.push_back(e); cycle_noshortcut<edge>(e.to(), g, use, in, E, res, e.id()); E.pop_back(); } } use[cur] = true; in[cur] = -1; } // accept_self_loop := trueなら自己辺も長さ1のサイクルとみなす template<typename edge> vec<edge> cycle_noshortcut(vec<vec<edge>> &g, bool accept_self_loop){ int n = g.size(); if(accept_self_loop){ for(int i = 0; i < n; i++){ for(auto &e : g[i]){ if(e.to() == e.from()){ return {e}; // 自己辺をサイクルと見なすか } } } } vec<bool> use(n, false); vec<int> in(n, -1); vec<edge> res, E; for(int i = 0; i < n; i++){ if(use[i]) continue; cycle_noshortcut<edge>(i, g, use, in, E, res, -1); if(!res.empty()) break; } return res; } // 全体の最小コスト閉路 // 重みあり O(V(V + E)logV) // 重みなし O(V(V + E)) template<typename edge> std::pair<typename edge::weight, vec<edge>> cycle_mincost(const vec<vec<edge>> &g, bool directed, bool weighted, bool accept_self_loop){ using weight = typename edge::weight; using pdv = std::pair<weight, int>; static constexpr weight inf = std::numeric_limits<weight>::max() / 2; auto chmin = [&](weight &a, weight b)->bool{ if(a > b){ a = b; return true; } return false; }; int n = g.size(); vec<vec<edge>> cpg = g; for(int v = 0; v < n; v++) std::sort(cpg[v].begin(), cpg[v].end(), [](edge &a, edge &b){return a.to() < b.to();}); std::priority_queue<pdv, vec<pdv>, std::greater<pdv>> q1; std::queue<pdv> q2; std::function<pdv()> get_top = [&]()->pdv{pdv ret = q1.top();q1.pop();return ret;}; std::function<void(pdv)> push = [&](pdv a)->void{q1.push(a);}; std::function<bool()> empty = [&]()->bool{return q1.empty();}; if(!weighted){ get_top = [&]()->pdv{pdv ret = q2.front();q2.pop();return ret;}; push = [&](pdv a)->void{q2.push(a);}; empty = [&]()->bool{return q2.empty();}; } weight ans = inf; vec<edge> E; for(int v = n - 1; v >= 0; v--){ vec<weight> dist(v + 1, inf); dist[v] = edge::z(); push({edge::z(), v}); vec<edge> par(v), unused; while(!empty()){ auto [d, u] = get_top(); if(dist[u] < d) continue; for(int i = 0; i < cpg[u].size(); i++){ int to = cpg[u][i].to(); if(to > v){ cpg[u].pop_back(); continue; } weight nxtd = d + cpg[u][i].wei(); if(chmin(dist[to], nxtd)){ par[to] = cpg[u][i]; push({nxtd, to}); }else if(par[u].id() != cpg[u][i].id()) unused.push_back(cpg[u][i]); } } weight pre_ans = ans; edge tmp_edge; if(!directed){ for(edge &e : unused){ if(dist[e.from()] == inf || dist[e.to()] == inf) continue; if(e.from() == e.to()){ if(accept_self_loop && e.to() == v && chmin(ans, e.wei())){ tmp_edge = e; // 自己辺をサイクルとみなす場合 } continue; } if(chmin(ans, e.wei() + dist[e.from()] + dist[e.to()])) tmp_edge = e; } }else{ for(edge &e : unused){ if(dist[e.from()] == inf) continue; if(accept_self_loop && e.to() == v && chmin(ans, e.wei() + dist[e.from()])){ tmp_edge = e; // 自己辺をサイクルとみなす場合 } if(e.from() != v && e.to() == v && chmin(ans, e.wei() + dist[e.from()])) tmp_edge = e; } } if(ans < pre_ans){ E.clear(); int a = tmp_edge.from(); while(a != v){ E.push_back(par[a]); a = par[a].from(); } std::reverse(E.begin(), E.end()); E.push_back(tmp_edge); a = tmp_edge.to(); while(a != v){ E.push_back(par[a].reverse()); a = par[a].from(); } } } return {ans, E}; } // vを含む最小コストの閉路 // 重みあり O((V + E)logV) // 重みなし O(V + E) template<typename edge> std::pair<typename edge::weight, vec<edge>> cycle_mincost_specific_vertex(vec<vec<edge>> &g, int v, bool directed, bool weighted, bool accept_self_loop){ using weight = typename edge::weight; using pdv = std::pair<weight, int>; static constexpr weight inf = std::numeric_limits<weight>::max() / 2; auto chmin = [&](weight &a, weight b)->bool{ if(a > b){ a = b; return true; } return false; }; int n = g.size(); std::priority_queue<pdv, vec<pdv>, std::greater<pdv>> q1; std::queue<pdv> q2; std::function<pdv()> get_top = [&]()->pdv{pdv ret = q1.top();q1.pop();return ret;}; std::function<void(pdv)> push = [&](pdv a)->void{q1.push(a);}; std::function<bool()> empty = [&]()->bool{return q1.empty();}; if(!weighted){ get_top = [&]()->pdv{pdv ret = q2.front();q2.pop();return ret;}; push = [&](pdv a)->void{q2.push(a);}; empty = [&]()->bool{return q2.empty();}; } weight ans = inf; vec<edge> E; vec<weight> dist(n, inf); dist[v] = edge::z(); push({edge::z(), v}); vec<edge> par(n), unused; // 無向辺の場合lca(from, to)がvであることがvを含むサイクルになる必要十分条件 // d1_ancestor[i] := iから辿ってどの深さ1のノードに辿り着くか vec<int> d1_ancestor(n, -1); while(!empty()){ auto [d, u] = get_top(); if(dist[u] < d) continue; if(par[u].from() == v) d1_ancestor[u] = u; else d1_ancestor[u] = d1_ancestor[par[u].from()]; for(int i = 0; i < g[u].size(); i++){ int to = g[u][i].to(); weight nxtd = d + g[u][i].wei(); if(chmin(dist[to], nxtd)){ par[to] = g[u][i]; push({nxtd, to}); }else if(par[u].id() != g[u][i].id()) unused.push_back(g[u][i]); //無向辺の逆流対策 } } edge tmp_edge; if(!directed){ for(edge &e : unused){ if(dist[e.from()] == inf || dist[e.to()] == inf) continue; if(e.from() == e.to()){ if(accept_self_loop && e.to() == v && chmin(ans, e.wei())){ tmp_edge = e; // 自己辺をサイクルと見なす場合 } continue; } if(d1_ancestor[e.from()] == d1_ancestor[e.to()]) continue; if(chmin(ans, e.wei() + dist[e.from()] + dist[e.to()])) tmp_edge = e; } }else{ for(edge &e : unused){ if(dist[e.from()] == inf) continue; if(accept_self_loop && e.to() == v && chmin(ans, e.wei() + dist[e.from()])){ tmp_edge = e; // 自己辺をサイクルと見なす場合 } if(e.from() != v && e.to() == v && chmin(ans, e.wei() + dist[e.from()])) tmp_edge = e; } } if(ans != inf){ int a = tmp_edge.from(); while(a != v){ E.push_back(par[a]); a = par[a].from(); } std::reverse(E.begin(), E.end()); E.push_back(tmp_edge); a = tmp_edge.to(); while(a != v){ E.push_back(par[a].reverse()); a = par[a].from(); } } return {ans, E}; } // 全ての辺を1度だけ使うウォークが存在するか // オイラー路が存在するための必要十分条件 // 無向グラフ : 奇次数の頂点が2個か0個 // 有向グラフ : 入次数と出次数の異なる頂点が0個または(2個かつその頂点の間に辺を1本足すと0個にできる) // 上の条件を満たさない場合は空のvectorを返す // 無向グラフのときは辺にユニークなidを割り振って逆流しないようにする template<typename edge> vec<edge> eulerian_trail_directed(vec<vec<edge>> g){ int n = g.size(), m = 0, x = -1, y = -1, z = -1; vec<int> in(n, 0), out(n); for(int i = 0; i < n; i++){ out[i] = g[i].size(); m += out[i]; for(auto &e : g[i]) in[e.t]++; } for(int i = 0; i < n; i++){ if(out[i] > 0) z = i; if(in[i] == out[i]) continue; if(in[i] > out[i] + 1 || in[i] + 1 < out[i]) return {}; if(in[i] == out[i] + 1){ if(y != -1) y = i; else return {}; } if(in[i] + 1 == out[i]){ if(x != -1) x = i; else return {}; } } if(x != -1) z = x; vec<edge> E, E1; vec<vec<edge>> E2(n); vec<bool> used_vertex(n, false); std::queue<int> q; // ベースとなるwalkを探す auto find_base_walk = [&](int v){ while(out[v]){ edge e = g[v].back(); g[v].pop_back(); int next = e.t; out[v]--; in[next]--; if(!used_vertex[v]){ used_vertex[v] = 1; q.push(v); } E1.push_back(e); v = next; } if(!used_vertex[v]){ used_vertex[v] = 1; q.push(v); } }; // vから初めてvに帰ってくるサイクルを探す auto find_cycle = [&](int v){ int tmp = v; while(out[v]){ edge e = g[v].back(); g[v].pop_back(); int next = e.t; in[v]--; out[next]--; if(!used_vertex[v]){ used_vertex[v] = 1; q.push(v); } E2[tmp].push_back(e); v = next; } }; find_base_walk(z); while(!q.empty()){ int tmp = q.front(); q.pop(); find_cycle(tmp); } std::fill(used_vertex.begin(), used_vertex.end(), 0); E2[z].insert(E2[z].end(), E1.begin(), E1.end()); used_vertex[z] = 1; auto dfs = [&](auto &&dfs, int cur)->void{ for(auto &e : E2[cur]){ E.push_back(e); if(!used_vertex[e.t] && e.t != cur){ dfs(dfs, e.t); used_vertex[e.t] = 1; } } }; dfs(dfs, z); if(E.size() != m) return {};// 例: グラフが連結でない場合など return E; } // 辺のidは[0, m)にする template<typename edge> vec<edge> eulerian_trail_undirected(vec<vec<edge>> g){ int n = g.size(), m = 0, x = -1, y = -1, z = -1; vec<int> deg(n); for(int i = 0; i < n; i++){ deg[i] = g[i].size(); m += deg[i]; if(deg[i] & 1){ if(x == -1) x = i; else if(y == -1) y = i; else return {}; } if(deg[i]) z = i; } assert((x == -1 && y == -1) || (x != -1 && y != -1)); m /= 2; if(x != -1) z = x; vec<edge> E, E1; vec<vec<edge>> E2(n); vec<bool> used_edge(m, false), used_vertex(n, false); std::queue<int> q; // ベースとなるwalkを探す auto find_base_walk = [&](int v){ while(deg[v]){ edge e = g[v].back(); g[v].pop_back(); if(used_edge[e.id()]) continue; int next = e.t; deg[v]--; deg[next]--; used_edge[e.id()] = 1; if(!used_vertex[v]){ used_vertex[v] = 1; q.push(v); } E1.push_back(e); v = next; } if(!used_vertex[v]){ used_vertex[v] = 1; q.push(v); } }; // vから初めてvに帰ってくるサイクルを探す auto find_cycle = [&](int v){ int tmp = v; while(deg[v]){ edge e = g[v].back(); g[v].pop_back(); if(used_edge[e.id()]) continue; int next = e.t; deg[v]--; deg[next]--; used_edge[e.id()] = 1; if(!used_vertex[v]){ used_vertex[v] = 1; q.push(v); } E2[tmp].push_back(e); v = next; } }; find_base_walk(z); while(!q.empty()){ int tmp = q.front(); q.pop(); while(deg[tmp]) find_cycle(tmp); } std::fill(used_vertex.begin(), used_vertex.end(), 0); E2[z].insert(E2[z].end(), E1.begin(), E1.end()); used_vertex[z] = 1; auto dfs = [&](auto &&dfs, int cur)->void{ for(auto &e : E2[cur]){ E.push_back(e); if(!used_vertex[e.t] && e.t != cur){ dfs(dfs, e.t); used_vertex[e.t] = 1; } } }; dfs(dfs, z); if(E.size() != m) return {};// 例: グラフが連結でない場合など return E; } /* // ! グラフが連結でない場合 // res[i] := iを含む閉路 O(V^2 + Elog^2V) // 全ての辺に[0, E)のuniqueな値を振っておく template<typename edge> vec<vec<edge>> undirected_cycle_detection_vv(vec<vec<edge>> &g){ int n = g.size(); tree<edge> t = bfs_tree<edge>(g, 0); vec<bool> used_edge{0}; for(int i = 0; i < n; i++){ for(edge &e : t.g[i]){ assert(0 <= e.id() && e.id() <= 1e7); while(used_edge.size() <= e.id()) used_edge.resize(used_edge.size() << 1); used_edge[e.id()] = true; } } t.hld_build(); t.bfs_build(); dual_segment_tree<range_set_get_any, edge*, edge*> seg(n, nullptr); for(int i = 0; i < n; i++){ for(edge &e : g[i]){ if(e.id() >= used_edge.size() || !used_edge[e.id()]){// bfs木に含まれない for(auto [l, r] : t.hld_p->unordered_path(e.from(), e.to())) seg.update(l, r, &e); if(e.id() < used_edge.size()) used_edge[e.id()] = true; } } } vec<vec<edge>> res(n); for(int i = 0; i < n; i++){ if(!res[i].empty()) continue; edge *e = seg.get(t.hld_p->index_vertex(i)); if(!e) continue;// iを含む閉路が無い vec<edge> E; int a = e->from(), b = e->to(), l = t.hld_p->lca(a, b); while(a != l){ E.push_back(t.bfs_p->get_parent_edge(a)); a = t.parent[a]; } std::reverse(E.begin(), E.end()); E.push_back(*e); while(b != l){ E.push_back(t.bfs_p->get_parent_edge(b).reverse()); b = t.parent[b]; } for(edge &e : E) if(res[e.from()].empty()) res[e.from()] = E; } return res; } */ }; #line 4 "a.cpp" int main(){ io_init(); // d[x] := 出次数 - 入次数 int n, m; std::cin >> n >> m; using edge = weighted_labeled_edge<int>; general_graph<edge> g(n); range(i, 0, m){ int a, b; std::cin >> a >> b; a--, b--; g.add_edge(a, {a, b, 1, i}); } vector<int> pos(n, 0); vector<edge*> E; vector<bool> 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, 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<edge> ans; simple_graph g2(n); range(i, 0, n){ for(auto e : g[i]){ if(e.w){ ans.push_back(e); g2.add_edge(e.s, {e.s, e.t}); } } } assert(graph_algorithm::cycle_noshortcut(g2.g, true).empty()); std::cout << n << " " << ans.size() << '\n'; range(i, 0, ans.size()) std::cout << ans[i].s + 1 << " " << ans[i].t + 1 << '\n'; }