use std::io::*; #[allow(dead_code)] fn getline() -> String { let mut ret = String::new(); std::io::stdin().read_line(&mut ret).ok(); return ret; } fn get_word() -> String { let mut stdin = std::io::stdin(); let mut u8b: [u8; 1] = [0]; loop { let mut buf: Vec = Vec::with_capacity(16); loop { let res = stdin.read(&mut u8b); if res.is_err() || res.ok().unwrap() == 0 || u8b[0] <= ' ' as u8 { break; } else { buf.push(u8b[0]); } } if buf.len() >= 1 { let ret = std::string::String::from_utf8(buf).unwrap(); return ret; } } } fn parse(s: &str) -> T { s.parse::().ok().unwrap() } #[allow(dead_code)] fn get() -> T { parse(&get_word()) } /** * Dinic's algorithm for maximum flow problem. * Verified by: yukicoder No.177 () * Min-cut (the second element of max_flow's returned values) is not verified. */ #[derive(Clone)] struct Edge { to: usize, cap: T, rev: usize, // rev is the position of the reverse edge in graph[to] } struct Dinic { graph: Vec>>, iter: Vec, zero: T, } impl Dinic where T: Clone, T: Copy, T: Ord, T: std::ops::AddAssign, T: std::ops::SubAssign, { fn bfs(&self, s: usize, level: &mut [Option]) { let n = level.len(); for i in 0 .. n { level[i] = None; } let mut que = std::collections::VecDeque::new(); level[s] = Some(0); que.push_back(s); while let Some(v) = que.pop_front() { for e in self.graph[v].iter() { if e.cap > self.zero && level[e.to] == None { level[e.to] = Some(level[v].unwrap() + 1); que.push_back(e.to); } } } } /* search augment path by dfs. * if f == None, f is treated as infinity. */ fn dfs(&mut self, v: usize, t: usize, f: Option, level: &mut [Option]) -> T { if v == t { return f.unwrap(); } while self.iter[v] < self.graph[v].len() { let i = self.iter[v]; let e = self.graph[v][i].clone(); if e.cap > self.zero && level[v] < level[e.to] { let newf = std::cmp::min(f.unwrap_or(e.cap), e.cap); let d = self.dfs(e.to, t, Some(newf), level); if d > self.zero { self.graph[v][i].cap -= d; self.graph[e.to][e.rev].cap += d; return d; } } self.iter[v] += 1; } self.zero } pub fn new(n: usize, zero: T) -> Self { Dinic { graph: vec![Vec::new(); n], iter: vec![0; n], zero: zero, } } pub fn add_edge(&mut self, from: usize, to: usize, cap: T) { let added_from = Edge { to: to, cap: cap, rev: self.graph[to].len() }; let added_to = Edge { to: from, cap: self.zero, rev: self.graph[from].len() }; self.graph[from].push(added_from); self.graph[to].push(added_to); } pub fn max_flow(&mut self, s: usize, t: usize) -> (T, Vec) { let mut flow = self.zero; let n = self.graph.len(); let mut level = vec![None; n]; loop { self.bfs(s, &mut level); if level[t] == None { let ret = (0 .. n).filter(|&i| level[i] == None) .collect(); return (flow, ret); } self.iter.clear(); self.iter.resize(n, 0); loop { let f = self.dfs(s, t, None, &mut level); if f <= self.zero { break; } flow += f; } } } } fn main() { let w = get(); let n = get(); let j: Vec = (0 .. n).map(|_| get()).collect(); let m = get(); let c: Vec = (0 .. m).map(|_| get()).collect(); let mut din = Dinic::new(n + m + 2, 0); for i in 0 .. n { din.add_edge(0, 2 + i, j[i]); } for i in 0 .. m { din.add_edge(2 + n + i, 1, c[i]); } for i in 0 .. m { let qi = get(); let mut lim = vec![1 << 32; n]; for _ in 0 .. qi { let x = get::() - 1; lim[x] = 0; } for j in 0 .. n { if lim[j] > 0 { din.add_edge(2 + j, 2 + n + i, lim[j]); } } } println!("{}", if din.max_flow(0, 1).0 >= w { "SHIROBAKO" } else { "BANSAKUTSUKITA" }); }