結果
| 問題 | No.2464 To DAG |
| ユーザー |
 tonegawa
|
| 提出日時 | 2023-09-09 17:11:53 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 25,654 bytes |
| コンパイル時間 | 3,250 ms |
| コンパイル使用メモリ | 152,596 KB |
| 実行使用メモリ | 55,984 KB |
| 最終ジャッジ日時 | 2024-06-27 09:54:03 |
| 合計ジャッジ時間 | 16,536 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | WA | - |
| testcase_02 | AC | 282 ms
55,984 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 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | AC | 2 ms
5,376 KB |
| testcase_20 | WA | - |
| testcase_21 | AC | 2 ms
5,376 KB |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | AC | 11 ms
11,416 KB |
| testcase_40 | WA | - |
ソースコード
#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 3 "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]){
use[cur] = true;
}else{
while(true){
edge *e = E.back();
E.pop_back();
e->i = 0;
if(e->s == cur) break;
else use[e->s] = false;
}
}
for(; pos[cur] < g[cur].size();){
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<edge> ans;
range(i, 0, n){
for(auto e : g[i]){
if(e.i == 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';
}