#line 1 "main.cpp" #include using namespace std; #include using namespace atcoder; #line 3 "/home/WebP/kyopro/lib/compress.hpp" template std::vector Compress(const std::vector& v) { std::vector xs = v; std::sort(xs.begin(), xs.end()); xs.erase(std::unique(xs.begin(), xs.end()), xs.end()); std::vector res(v.size()); for (int i = 0; i < (int)v.size(); i++) { res[i] = std::lower_bound(xs.begin(),xs.end(),v[i])-xs.begin(); } return res; } #line 1 "/home/WebP/kyopro/lib/edge.hpp" struct Edge { int to; long long cost; Edge() : to(0), cost(0) {} Edge(int to, long long cost) : to(to), cost(cost) {} }; struct Edge2 { int from, to; long long cost; Edge2() : from(0), to(0), cost(0) {} Edge2(int from, int to, long long cost) : from(from), to(to), cost(cost) {} bool operator==(const Edge2& other) const { return cost == other.cost && from == other.from && to == other.to; } bool operator>(const Edge2& other) const { if (cost != other.cost) return cost > other.cost; if (from != other.from) return from > other.from; return to > other.to; } bool operator>=(const Edge2& other) const { return *this > other || *this == other; } bool operator<(const Edge2& other) const { if (cost != other.cost) return cost < other.cost; if (from != other.from) return from < other.from; return to < other.to; } bool operator<=(const Edge2& other) const { return *this < other || *this == other; } }; #line 2 "/home/WebP/kyopro/lib/eratosthenes.hpp" std::vector make_sieve(int n) { std::vector is_prime(n,true); is_prime[0] = is_prime[1] = false; for (int i = 2; i*i < n; i++) { if (is_prime[i]) { for (int j = i * i; j < n; j += i) { is_prime[j] = false; } } } return is_prime; } std::vector Eratosthenes(int n) { std::vector is_prime = make_sieve(n); std::vector primes; for (int i = 0; i < n; i++) { if (is_prime[i]) primes.push_back(i); } return primes; } #line 2 "/home/WebP/kyopro/lib/gen.hpp" int randint(int l, int r) { static std::mt19937 mt(std::random_device{}()); std::uniform_int_distribution dist(l, r); return dist(mt); } long double randdouble(long double l, long double r) { static std::mt19937 mt(std::random_device{}()); std::uniform_real_distribution dist(l, r); return dist(mt); } #line 5 "/home/WebP/kyopro/lib/interval_set.hpp" class IntervalSet { }; // e.g. ABC435-E "Cover Query" (https://atcoder.jp/contests/abc435/tasks/abc435_e) void solve_interval_set() { int n, q; std::cin >> n >> q; std::set> s; int ans = n; for(int qi = 0; qi < q; qi++) { int l, r; std::cin >> l >> r; l--; auto it = s.lower_bound({l,-1}); if(it != s.begin() && prev(it)->second >= l) it--; while(it != s.end() && it->first <= r) { auto [nl,nr] = *it; ans += nr-nl; l = std::min(l,nl); r = std::max(r,nr); s.erase(it++); } s.emplace(l,r); ans -= r-l; std::cout << ans << '\n'; } } #line 4 "/home/WebP/kyopro/lib/is_bipartite.hpp" bool is_bipartite() { return false; } // e.g. ABC282-D "Make Bipartite 2" (https://atcoder.jp/contests/abc282/tasks/abc282_d) long long c2_is_bipartite(long long r) {return r*(r-1)/2;} void solve_is_bipartite() { int n, m; std::cin >> n >> m; std::vector> to(n); for(int i = 0; i < m; i++) { int u, v; std::cin >> u >> v; u--; v--; to[u].push_back(v); to[v].push_back(u); } std::vector c(n,-1); long long ng = 0; bool ok = true; for(int s = 0; s < n; s++) { if(c[s] != -1) continue; long long w = 0, b = 0; std::queue q; q.push(s); c[s] = 0; while(q.size()) { int u = q.front(); q.pop(); if(c[u] == 0) w++; else b++; for(int v : to[u]) { if(c[v] != -1) { if(c[u] == c[v]) { ok = false; } continue; } c[v] = 1-c[u]; q.push(v); } } ng += c2_is_bipartite(w)+c2_is_bipartite(b); } std::cout << (ok ? c2_is_bipartite(n)-ng-m : 0) << "\n"; } #line 4 "/home/WebP/kyopro/lib/make_rle.hpp" std::vector> make_rle(std::string s) { std::vector> rle; for (char c : s) { if (rle.empty() || rle.back().first != c) { rle.emplace_back(c,1); } else { rle.back().second++; } } return rle; } #line 2 "/home/WebP/kyopro/lib/make_vector.hpp" template auto make_vector(const T& value, std::size_t n) { return std::vector(n, value); } template auto make_vector(const T& value, std::size_t n, Sizes... sizes) { return std::vector(n, make_vector(value, sizes...)); } #line 1 "/home/WebP/kyopro/lib/power.hpp" long long power(long long a, long long n) { long long ret = 1; while(n) { if(n & 1) ret *= a; a *= a; n >>= 1; } return ret; } #line 4 "/home/WebP/kyopro/lib/rotate.hpp" inline void Rotate(std::vector& a) { int h = a.size(); int w = a[0].size(); std::vector b(w, std::string(h, ' ')); for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { b[j][h - 1 - i] = a[i][j]; } } a = std::move(b); } inline void Rotate(std::vector& a, int k) { k = (k % 4 + 4) % 4; while (k--) Rotate(a); } template void Rotate(std::vector>& a) { int h = a.size(); int w = a[0].size(); std::vector> b( w, std::vector(h) ); for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { b[j][h - 1 - i] = a[i][j]; } } a = std::move(b); } template void Rotate(std::vector>& a, int k) { k = (k % 4 + 4) % 4; while (k--) Rotate(a); } #line 2 "/home/WebP/kyopro/lib/unionfind.hpp" class UnionFind { private: std::vector par, siz; int cnt = -1; public: UnionFind(int n) { init(n); } void init(int n) { par.assign(n, -1); siz.assign(n, 1); cnt = n; } int root(int v) { if (par[v] == -1) return v; return par[v] = root(par[v]); } bool merge(int u, int v) { int RootU = root(u); int RootV = root(v); if (RootU == RootV) return false; if (siz[RootU] < siz[RootV]) { par[RootU] = RootV; siz[RootV] = siz[RootU] + siz[RootV]; } else { par[RootV] = RootU; siz[RootU] = siz[RootU] + siz[RootV]; } cnt--; return true; } bool same(int u, int v) { return root(u) == root(v); } int count() { return cnt; } int count(int v) { return siz[root(v)]; } int size(int v) { return siz[v]; } }; #line 7 "/home/WebP/kyopro/lib/util.hpp" #include using mint = atcoder::modint998244353; using ll = long long; using ld = long double; using P = std::pair; using PL = std::pair; template using greater_queue = std::priority_queue, std::greater>; template using uset = std::unordered_set; template using umap = std::unordered_map; #define rep(i,s,n) for (int i = (s); i < (n); i++) #define rep1(i,s,n) for (int i = (s); i <= (n); i++) #define REP(i,n,s) for (int i = (n)-1; i >= s; i--) #define REP1(i,n,s) for (int i = (n); i >= s; i--) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define sz(a) (int)(a).size() const std::vector di = {0,0,-1,1}, dj = {-1,1,0,0}; // LRUD template bool chmax(T& a, const T& b) { return (a < b ? (a = b, true) : false); } template bool chmin(T& a, const T& b) { return (a > b ? (a = b, true) : false); } void YesNo(bool b) { std::cout << (b ? "Yes\n" : "No\n"); } template std::istream& operator>>(std::istream& is, std::pair& p) { is >> p.first >> p.second; return is; } template std::istream& operator>>(std::istream& is, std::vector& v) { for (T& x : v) { is >> x; } return is; } template std::ostream& operator<<(std::ostream& os, const atcoder::static_modint& x) { return os << x.val(); } std::ostream& operator<<(std::ostream& os, const atcoder::modint& x) { return os << x.val(); } #line 3 "/home/WebP/kyopro/lib/vector.hpp" struct V { long long x, y; V(long long x=0, long long y=0): x(x), y(y) {} V& operator+=(const V& v) { x += v.x; y += v.y; return *this;} V operator+(const V& v) const { return V(*this) += v;} V& operator-=(const V& v) { x -= v.x; y -= v.y; return *this;} V operator-(const V& v) const { return V(*this) -= v;} V& operator*=(long long s) { x *= s; y *= s; return *this;} V operator*(long long s) const { return V(*this) *= s;} V& operator/=(long long s) { x /= s; y /= s; return *this;} V operator/(long long s) const { return V(*this) /= s;} long long dot(const V& v) const { return x*v.x + y*v.y;} long long cross(const V& v) const { return x*v.y - v.x*y;} long long norm2() const { return x*x + y*y;} long long norm() const { return sqrt(norm2());} V normalize() const { return *this/norm();} V rotate90() const { return V(y, -x);} }; std::istream& operator>>(std::istream& is, V& v) { is >> v.x >> v.y; return is; } std::ostream& operator<<(std::ostream& os, const V& v) { os<<"("<> h >> w; vector a(h,vector(w)); rep(i,0,h) rep(j,0,w) cin >> a[i][j]; rep(i,0,h) rep(j,0,w) rep(ni,0,h) rep(nj,0,w) { if (a[i][j] > 0 || a[ni][nj] > 0) { cout << "infinite\n"; return; } } cout << "finite\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); int t = 1; cin >> t; rep(ti,0,t) solve(); return 0; }