結果
| 問題 | No.2464 To DAG |
| ユーザー |
 tonegawa
|
| 提出日時 | 2023-09-09 18:52:21 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 42,082 bytes |
| コンパイル時間 | 2,114 ms |
| コンパイル使用メモリ | 163,156 KB |
| 実行使用メモリ | 64,304 KB |
| 最終ジャッジ日時 | 2024-06-27 11:28:24 |
| 合計ジャッジ時間 | 15,626 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 243 ms
64,304 KB |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | AC | 157 ms
26,076 KB |
| testcase_15 | AC | 237 ms
32,320 KB |
| testcase_16 | AC | 105 ms
19,476 KB |
| testcase_17 | AC | 15 ms
5,888 KB |
| testcase_18 | AC | 60 ms
14,072 KB |
| testcase_19 | AC | 2 ms
5,376 KB |
| testcase_20 | AC | 2 ms
5,376 KB |
| testcase_21 | AC | 2 ms
5,376 KB |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | AC | 42 ms
10,380 KB |
| testcase_27 | AC | 266 ms
40,520 KB |
| testcase_28 | AC | 265 ms
40,632 KB |
| testcase_29 | AC | 262 ms
39,624 KB |
| testcase_30 | AC | 184 ms
25,924 KB |
| testcase_31 | AC | 153 ms
23,208 KB |
| testcase_32 | AC | 140 ms
22,252 KB |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | AC | 21 ms
19,584 KB |
| testcase_40 | AC | 20 ms
19,584 KB |
ソースコード
#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;
}
}
use[cur] = 1;
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;
}
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';
}