#include #include #include #include #include using namespace std; constexpr int inf = 987654321; struct Edge { int dst, rev; int capa; int cost; }; class Graph { protected: int size; vector> g; public: Graph(int size) : size(size) { g.resize(size); } void add_edge(int src, int dst, int capa); void add_edge(int src, int dst, int capa, int cost); int max_flow(int s, int t) { throw; } int min_cost_flow_ford(int s, int t, int flow); // ベルマンフォード int min_cost_flow_dijk(int s, int t, int flow); // ダイクストラ }; class FordFulkerson : public Graph { vector used; int dfs(int v, int t, int flow); public: FordFulkerson(int size) : Graph(size) {} int max_flow(int s, int t); }; class Dinic : public Graph { vector level, iter; void bfs(int s); int dfs(int v, int t, int flow); public: Dinic(int size) : Graph(size) {} int max_flow(int s, int t); }; void Graph::add_edge(int src, int dst, int capa) { add_edge(src, dst, capa, 0); } void Graph::add_edge(int src, int dst, int capa, int cost) { g[src].push_back(Edge({dst, int(g[dst].size()), capa, cost})); g[dst].push_back(Edge({src, int(g[src].size())-1, 0, -cost})); } int Graph::min_cost_flow_ford(int s, int t, int flow) { int res = 0; vector prev_v(size), prev_e(size); vector dist; while(flow > 0) { dist.assign(size, inf); dist[s] = 0; bool update = true; while(update) { update = false; for(int v=0; v 0 && dist[e.dst] > dist[v] + e.cost) { dist[e.dst] = dist[v] + e.cost; prev_v[e.dst] = v; prev_e[e.dst] = i; update = true; } } } } if(dist[t] == inf) { return inf; } int d = flow; for(int v=t; v!=s; v=prev_v[v]) { d = min(d, g[prev_v[v]][prev_e[v]].capa); } flow -= d; res += d * dist[t]; for(int v=t; v!=s; v=prev_v[v]) { Edge& e = g[prev_v[v]][prev_e[v]]; e.capa -= d; g[v][e.rev].capa += d; } } return res; } int Graph::min_cost_flow_dijk(int s, int t, int flow) { int res = 0; vector prev_v(size), prev_e(size); vector h(size); while(flow > 0) { vector dist(size, inf); dist[s] = 0; queue> que; // 最短距離、番号 que.emplace(0, s); while(!que.empty()) { int c, v; tie(c, v) = que.front(); que.pop(); if(dist[v] < c) { continue; } for(int i=0; i 0 && dist[e.dst] > dist[v] + e.cost + h[v] - h[e.dst]) { dist[e.dst] = dist[v] + e.cost + h[v] - h[e.dst]; prev_v[e.dst] = v; prev_e[e.dst] = i; que.emplace(dist[e.dst], e.dst); } } } if(dist[t] == inf) { return inf; } for(int v=0; v 0) { e.capa -= d; g[e.dst][e.rev].capa += d; return d; } } return 0; } int FordFulkerson::max_flow(int s, int t) { int res = 0; while(true) { used.assign(size, false); int flow = dfs(s, t, inf); if(flow == 0) { return res; } res += flow; if(res >= inf) { return inf; } } } void Dinic::bfs(int s) { level.assign(size, -1); queue que; level[s] = 0; que.push(s); while(!que.empty()) { int v = que.front(); que.pop(); for(Edge& e : g[v]) { if(e.capa > 0 && level[e.dst] < 0) { level[e.dst] = level[v] + 1; que.push(e.dst); } } } } int Dinic::dfs(int v, int t, int flow) { if(v == t) { return flow; } for(int& i=iter[v], n=g[v].size(); i= level[e.dst]) { continue; } int d = dfs(e.dst, t, min(flow, e.capa)); if(d > 0) { e.capa -= d; g[e.dst][e.rev].capa += d; return d; } } return 0; } int Dinic::max_flow(int s, int t) { int res = 0; while(true) { bfs(s); if(level[t] < 0) { return res; } iter.assign(size, 0); int flow; while((flow = dfs(s, t, inf)) > 0) { res += flow; if(res >= inf) { return inf; } } } } int main(void) { int w, n; scanf("%d%d", &w, &n); vector J(n); for(int i=0; i C(m); for(int i=0; i> G(n, vector(m, true)); // G[n][m] for(int i=0; i= w; puts(able ? "SHIROBAKO" : "BANSAKUTSUKITA"); return 0; }