#include #include #include #include #include #include #include #define rep(i,n) for (ll i = 0;i < (ll)(n);i++) #define Yes cout << "Yes" << endl// YESの短縮 #define No cout << "No" << endl// NOの短縮 #define rtr0 return(0)//return(0)の短縮 #define gyakugen(x) modpow(x,mod - 2,mod); #define anothergyakugen(x) modpow(x,anothermod - 2,anothermod); using namespace std; using ll = long long;//63bit型整数型 using ld = long double;//doubleよりも長い値を保存できるもの using ull = unsigned long long;//符号がない64bit型整数 ll mod = 998244353; ll anothermod = 1000000007; ll MINF = -5000000000000000000; ll INF = 5000000000000000000; ll BAD = -1; vectortate = {0,-1,0,1};//グリッド上の全探索時の四方向の上下のチェック vectoryoko = {1,0,-1,0};//グリッド上の全探索時の四方向の右左のチェック vectoreightx = {0,-1,-1,-1,0,1,1,1};//グリッド上の全探索時の八方向の上下のチェック vectoreighty = {1,1,0,-1,-1,-1,0,1};//グリッド上の全探索時の八方向の右左のチェック vectorhexsax = {0,1,1,0,-1,-1}; vectorhexsay = {1,1,0,-1,-1,0}; //返り値は素数のリスト。 vector < bool > isprime; vector < ll > Era(int n){//書き方 vector[] = Era(x); とやるとxまでの素数が出てくる。 isprime.resize(n, true); vector < ll > res; isprime[0] = false; isprime[1] = false; for(ll i = 2; i < n; ++i) isprime[i] = true; for(ll i = 2; i < n; ++i) { if(isprime[i]) { res.push_back(i); for(ll j = i * 2; j < n; j += i) isprime[j] = false; } } return res; } //      素数判定 21~35 long long modpow(long long a, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } // モッドを使った累乗 /*ll ans = INF; ll N,M,K; vector>>graph; void DFS(set&next,set&past,ll &cost){ if(past.size() == N){ ans = min(ans,cost%K); return; } if(next.empty() == true)return; ll a = *next.begin(); next.erase(a); for(ll i = 0;i> N >> M; vector>A(N,vector(0)); ll count = 1; for(ll x = 0;x>ans(0); for(ll i = 0;i