codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2006.md (35929B)


      1 Source: https://codeforces.com/blog/entry/133382
      2 
      3 [2007A - Dora's Set](/contest/2007/problem/A "Codeforces Round 969 (Div. 2)")
      4 
      5 **Hint 1**
      6 
      7 How many odd integers are there in a pair $(a, b, c)$?
      8 
      9 **Answer**
     10 
     11 At least 2.
     12 
     13 **Hint 2**
     14 
     15 It's always better to put **exactly $2$** odd integers and **exactly $1$** even integer in one pair of $(a, b, c)$. Is there a way to always choose optimal $(a, b, c)$?
     16 
     17 **Hint 3**
     18 
     19 Try consecutive integers.
     20 
     21 **Tutorial**
     22 
     23 Tutorial is loading...
     24 
     25 **Implementation**
     26 
     27 ```
     28 T = int(input())
     29  
     30 for _ in range(T) :
     31 	l, r = map(int, input().split())
     32 	print(((r + 1) // 2 - l // 2) // 2)
     33 ```
     34 
     35 [2007B - Index and Maximum Value](/contest/2007/problem/B "Codeforces Round 969 (Div. 2)")
     36 
     37 **Hint**
     38 
     39 Consider the position of the maximum value in one array. If there's multiple maximum values, choose any. What can you observe?
     40 
     41 **Answer**
     42 
     43 The position of the maximum value never changes. That is, if one element is the maximum value in the beginning, it will always be.
     44 
     45 **Tutorial**
     46 
     47 Tutorial is loading...
     48 
     49 **Implementation**
     50 
     51 ```
     52 T = int(input())
     53  
     54 for _ in range(T) :
     55 	n, m = map(int, input().split())
     56 	v = max(map(int, input().split()))
     57 	for __ in range(m) :
     58 		c, l, r = input().split()
     59 		l = int(l)
     60 		r = int(r)
     61 		if (l <= v <= r) :
     62 			if (c == '+') :
     63 				v = v + 1
     64 			else :
     65 				v = v - 1
     66 		print(v, end = ' ' if __ != m - 1 else '\n')
     67 ```
     68 
     69 [2007C - Dora and C++](/contest/2007/problem/C "Codeforces Round 969 (Div. 2)")
     70 
     71 **Hint1**
     72 
     73 If you can perform an operation that decreases $a$ or $b$ from an element, will it be different?
     74 
     75 **Answer**
     76 
     77 No. Decrease an element by $a$ is the same as increasing all other elements by $a$, as it does not affect the range.
     78 
     79 **Hint2**
     80 
     81 If $a = b$, can you solve the problem?
     82 
     83 **Tutorial**
     84 
     85 Tutorial is loading...
     86 
     87 **Implementation**
     88 
     89 ```
     90 import math
     91  
     92 T = int(input())
     93 for _ in range(T) :
     94 	n, a, b = map(int, input().split())
     95 	d = math.gcd(a, b)
     96 	a = list(map(int, input().split()))
     97 	a = [x % d for x in a]
     98 	a.sort()
     99 	res = a[n - 1] - a[0]
    100 	for i in range(1, n) :
    101 		res = min(res, a[i - 1] + d - a[i])
    102 	print(res)
    103 ```
    104 
    105 [2006A - Iris and Game on the Tree](/contest/2006/problem/A "Codeforces Round 969 (Div. 1)")
    106 
    107 **Hint1**
    108 
    109 How to calulate the weight of a leaf quickly?
    110 
    111 **Hint2**
    112 
    113 Consider a formed string. Let's delete useless part that won't contribute to the count of $\tt{01}$ and $\tt{10}$ substrings. What will be the rest?
    114 
    115 **Answer**
    116 
    117 A string with each pair of adjacent bits different. For example, $\tt{110001}\rightarrow\tt{101}$. Then what decides whether the weight is zero or not?
    118 
    119 **Hint3**
    120 
    121 The root is somehow important. When to fill $s_1$?
    122 
    123 **Tutorial**
    124 
    125 Tutorial is loading...
    126 
    127 **Implementation**
    128 
    129 ```
    130 T = int(input())
    131  
    132 for _ in range(T) :
    133     n = int(input())
    134     x, y, z, w = 0, 0, 0, 0
    135     deg = [0] * (n + 1)
    136     for __ in range(n - 1) :
    137         u, v = map(int, input().split())
    138         deg[u] += 1
    139         deg[v] += 1
    140     s = " " + input()
    141     for i in range(2, n + 1) :
    142         if deg[i] == 1 :
    143             if s[i] == '?' :
    144                 z += 1
    145             elif s[i] == '0' :
    146                 x += 1
    147             else :
    148                 y += 1
    149         elif s[i] == '?' :
    150             w += 1
    151     if s[1] == '0' :
    152         print(y + (z + 1) // 2)
    153     elif s[1] == '1' :
    154         print(x + (z + 1) // 2)
    155     else :
    156         print(max(x, y) + (z + (w % 2 if x == y else 0)) // 2)
    157 ```
    158 
    159 [2006B - Iris and the Tree](/contest/2006/problem/B "Codeforces Round 969 (Div. 1)")
    160 
    161 **Titbits**
    162 
    163 The previous statement of the problem did not directly tell you that the vertices are numbered by dfs order. It was changed to make the statement more readable. Can you prove that the following property is the same as telling you the vertices are numbered by dfs order?
    164 
    165 **previous version**
    166 
    167 For any three nodes $i,j,k$ that $1\le i \lt j \lt k\le n$, if $i$ is not an ancestor of $j$, then $i$ won't be an ancestor of $k$.
    168 
    169 **proof**
    170 
    171 Let's still focus on "the vertex numbers in one subtree are consecutive". Suppose it's not consecutive: Let the minimum vertex number be $i$(the root, for $p_i \lt i$), the maximum vertex number be $k$, and one of the lost vertex number be $j$, you can see that $i$ is an ancestor of $k$ but not an ancestor of $j$. So the conslusion is proved.
    172 
    173 **Hint1**
    174 
    175 On a tree with nodes numbered with dfs order, we have to find the distance between two consecutive nodes. What can you think of?
    176 
    177 **Answer**
    178 
    179 Each edge is passed by exactly two of the paths.
    180 
    181 **Hint2**
    182 
    183 How to calculate the maximum value of $\text{dist}(i,(i\bmod n)+1)$? Is it different when the weight of all of its edges are known?
    184 
    185 **Tutorial**
    186 
    187 Tutorial is loading...
    188 
    189 **Implementation**
    190 
    191 ```
    192 #include <bits/stdc++.h>
    193  
    194 namespace FastIO {
    195 	template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }
    196 	template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar(x % 10 ^ '0'); }
    197 	template <typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x); }
    198 	template <typename T> inline void print(T x, char en) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x), putchar(en); }
    199 }; using namespace FastIO;
    200  
    201 #define MAXN 200001
    202 int fa[MAXN], dep[MAXN];
    203 int c1[MAXN], c2[MAXN], len[MAXN];
    204  
    205 void solve() {
    206 	int N = read<int>(); long long w = read<long long>();
    207 	for (int i = 2; i <= N; ++i) fa[i] = read<int>();
    208 	for (int i = 2; i <= N; ++i) dep[i] = dep[fa[i]] + 1;
    209 	for (int i = 1; i <= N; ++i) len[i] = c1[i] = 0;
    210 	for (int i = 1, x, y; i <= N; ++i) {
    211 		x = i, y = (i == N ? 1 : i + 1);
    212 		while (x != y) {
    213 			if (dep[x] < dep[y]) std::swap(x, y);
    214 			(c1[x] ? c2[x] : c1[x]) = i, x = fa[x], ++len[i];
    215 		}
    216 	}
    217 	long long sum = 0, sur = N;
    218 	for (int i = 1, x; i < N; ++i) {
    219 		x = read<int>(), sum += read<long long>();
    220 		if ((--len[c1[x]]) == 0) --sur;
    221 		if ((--len[c2[x]]) == 0) --sur;
    222 		print<long long>(sum * 2 + sur * (w - sum), " \n"[i == N - 1]);
    223 	}
    224 }
    225  
    226 int main() { int T = read<int>(); while (T--) solve(); return 0; }
    227 ```
    228 
    229 **Bonus**
    230 
    231 Can you solve the problem if the nodes are not numbered by dfs order?
    232 
    233 [2006C - Eri and Expanded Sets](/contest/2006/problem/C "Codeforces Round 969 (Div. 1)")
    234 
    235 **Hint1**
    236 
    237 Let's try to judge whether an array is brilliant, and try to sort it first. What happens if we minus $1$ from each element?
    238 
    239 **Answer**
    240 
    241 Nothing will change.
    242 
    243 **Hint2**
    244 
    245 We only care about the relative positions between the elements. Let's consider the difference array $b$ of array $a$: $b_i=a_i-a_{i-1}(i\ge 2)$.
    246 
    247 **Hint3**
    248 
    249 What will the difference array look like after no more operations can be done?
    250 
    251 **Tutorial**
    252 
    253 Tutorial is loading...
    254 
    255 **Implementation - two pointers**
    256 
    257 ```
    258 #include<bits/stdc++.h>
    259 using namespace std;
    260 #define int         long long
    261 #define pii         pair<int,int>
    262 #define all(v)      v.begin(),v.end()
    263 #define pb          push_back
    264 #define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
    265 #define over(x)     {cout<<x<<endl;return;}
    266 #define cntbit(x)   __buitin_popcount(x)
    267 int n;
    268 int a[400005],lsteq[400005];
    269 struct two_pointers{
    270 	int l,r,mid;
    271 	int val[400005],rt;
    272 	void init(){
    273 		l=r=mid=rt=0;
    274 		val[0]=a[0];
    275 	}
    276 	inline void addr(){++r;rt=__gcd(rt,a[r]);}
    277 	inline void addl(){if(l+1>r)addr();++l;if(l>mid){rt=0,mid=r;val[mid]=a[mid];
    278 	for(int i=mid-1;i>=l;--i)val[i]=__gcd(val[i+1],a[i]);}}
    279 	inline int query(){return __gcd(val[l],rt);}
    280 };
    281 void Main() {
    282 	cin>>n;
    283 	REP(i,0,n)cin>>a[i];
    284 	REP(i,1,n)a[n-i]-=a[n-i-1];
    285 	REP(i,1,n)a[i-1]=llabs(a[i]);
    286 	--n;
    287 	lsteq[n]=n;
    288 	for(int i=n-1;i>=0;--i)lsteq[i]=(a[i]? i:lsteq[i+1]);
    289 	two_pointers p;p.init();
    290 	int ans=1,cnt=1;
    291 	REP(i,0,n)if(lsteq[i]==i){
    292 		while(p.l<i)p.addl();
    293 		while(p.r<n&&cntbit(p.query())>1)p.addr();
    294 		ans+=(n-p.r)*cnt+1;cnt=1;
    295 	}else ans+=lsteq[i]-i+1,++cnt;
    296 	cout<<ans<<endl;
    297 }
    298 void TC() {
    299 	int tc=1;
    300 	cin>>tc;
    301 	while(tc--){
    302 		Main();
    303 		cout.flush();
    304 	}
    305 }
    306 signed main() {
    307 	return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
    308 }
    309 ```
    310 
    311 **Implementation - sparse table**
    312 
    313 ```
    314 #include<bits/stdc++.h>
    315 using namespace std;
    316 #define int         long long
    317 #define pii         pair<int,int>
    318 #define all(v)      v.begin(),v.end()
    319 #define pb          push_back
    320 #define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
    321 #define over(x)     {cout<<x<<endl;return;}
    322 #define cntbit(x)   __buitin_popcount(x)
    323 int n;
    324 int a[400005],res[400005],lsteq[400005];
    325 int st[400005][20];
    326 int query(int l,int r){
    327 	int s=__lg(r-l+1);
    328 	return __gcd(st[l][s],st[r-(1<<s)+1][s]);
    329 }
    330 void Main() {
    331 	cin>>n;
    332 	REP(i,0,n)cin>>a[i];
    333 	--n;
    334 	if(!n)over(1)
    335 	REP(i,0,n)st[i][0]=llabs(a[i]-a[i+1]);
    336 	REP(j,0,__lg(n)){
    337 		REP(i,0,n-(1<<(j+1))+1){
    338 			st[i][j+1]=__gcd(st[i][j],st[i+(1<<j)][j]);
    339 		}
    340 	}
    341 	lsteq[n]=n;
    342 	for(int i=n-1;i>=0;--i)lsteq[i]=(a[i]==a[i+1]? lsteq[i+1]:i);
    343 	int ans=1;
    344 	int l=0,r=0;
    345 	REP(i,0,n){
    346 		l=max(l,lsteq[i]);r=max(r,l);
    347 		while(r<n&&cntbit(query(l,r))>1)++r;
    348 		ans+=n-r;ans+=lsteq[i]-i+1;
    349 	}
    350 	cout<<ans<<endl;
    351 }
    352 void TC() {
    353 	int tc=1;
    354 	cin>>tc;
    355 	while(tc--){
    356 		Main();
    357 		cout.flush();
    358 	}
    359 }
    360 signed main() {
    361 	return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
    362 }
    363 ```
    364 
    365 **Bonus**
    366 
    367 There's a harder but similar version of the problem. Can you solve it?
    368 
    369 There're $q$ queries: $L,R,k$. Find the number of pairs $(l,r)$ that $L\le l\le r\le R$, and $(\lvert Q({a_l\dots a_r}) \rvert-1) \cdot k\ge \max(a_l\dots a_r) - \min(a_l\dots a_r) $, where $Q(array)$ means the result of putting the array into the set.
    370 
    371 [2006D - Iris and Adjacent Products](/contest/2006/problem/D "Codeforces Round 969 (Div. 1)")
    372 
    373 **Hint1**
    374 
    375 Let's use another way to describe the problem. Let's define an array good, that it can be reordered to satisfy the condition. How many numbers do we have to change to make it good?
    376 
    377 To handle this, we need to know what is the optimal way to reorder an array.
    378 
    379 **Hint2**
    380 
    381 Sort the array. Suppose $a_1$ is the minimum and $a_n$ is the maximum. Where to place the two elements? Can you prove this is optimal?
    382 
    383 **Hint3**
    384 
    385 How to maintain the answer better using the properties?
    386 
    387 **Tutorial**
    388 
    389 Tutorial is loading...
    390 
    391 **Implementation**
    392 
    393 ```
    394 #include<bits/stdc++.h>
    395 using namespace std;
    396 #define all(v)      v.begin(),v.end()
    397 #define pb          push_back
    398 #define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
    399 #define over(x)     {cout<<(x)<<endl;return;}
    400 int n,q,r;
    401 int a[300005];
    402 int sum[300005];
    403 int ql[300005],qr[300005];
    404 int ans[300005];
    405 int cnt[300005],cnt2[300005];
    406 void Main() {
    407 	cin>>n>>q>>r;
    408 	REP(i,0,n)cin>>a[i];
    409 	sum[0]=0;
    410 	int B=sqrt(r);
    411 	REP(i,0,n)sum[i+1]=sum[i]+(a[i]<=B);
    412 	REP(i,0,q){
    413 		int x,y;
    414 		cin>>x>>y;
    415 		--x,--y;
    416 		ql[i]=x;qr[i]=y;
    417 		ans[i]=0;
    418 		if(sum[y+1]-sum[x]<(y-x+1)/2)ans[i]=(y-x+1)/2-sum[y+1]+sum[x];
    419 	}
    420 	REP(i,0,B){
    421 		REP(j,0,n+1)cnt[j]=cnt2[j]=0;
    422 		REP(j,0,n){
    423 			cnt[j+1]=cnt[j]+(a[j]<=i);
    424 			cnt2[j+1]=cnt2[j]+(a[j]<=r/(i+1));
    425 		}
    426 		REP(j,0,q){
    427 			int x=ql[j],y=qr[j],l=y-x+1;
    428 			int c1=cnt2[y+1]-cnt2[x],c2=cnt[y+1]-cnt[x];
    429 			ans[j]=max(ans[j],min((l-c1-c2+1)/2,l/2-c2));
    430 		}
    431 	}
    432 	REP(i,0,q)cout<<ans[i]<<' ';
    433 	cout<<endl;
    434 }
    435 void TC() {
    436     int tc=1;
    437     cin>>tc;
    438 	while(tc--){
    439 		Main();
    440 		cout.flush();
    441 	}
    442 }
    443 signed main() {
    444 	return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
    445 }
    446 /*
    447 1. CLEAR the arrays (ESPECIALLY multitests)
    448 2. DELETE useless output
    449  */
    450 ```
    451 
    452 [2006E - Iris's Full Binary Tree](/contest/2006/problem/E "Codeforces Round 969 (Div. 1)")
    453 
    454 **Hint1**
    455 
    456 Consider the degress of vertices in a binary tree. What can you observe?
    457 
    458 **Answer**
    459 
    460 The root has degree $2$, the non-leaf nodes different from the root have degree $3$, the leaf nodes have degree $1$. The degree of every node is not greater than $3$.
    461 
    462 **Hint2**
    463 
    464 Choose a root. It should have degree $\le 2$. Is it always possible to build a binary tree on the initial tree if all nodes have degree $\le 3$? What will be the depth of the binary tree with the given root?
    465 
    466 **Answer**
    467 
    468 It's always possible to build the binary tree, and the depth of the tree is the maximum distance from the root to any nodes in the tree.
    469 
    470 **Hint3**
    471 
    472 Consider the binary depth of the full tree. We should to go over every possible root, but how to find the maximum distance from the root to other nodes? Are there any special nodes?
    473 
    474 **Hint4**
    475 
    476 Diameter.
    477 
    478 **Hint5**
    479 
    480 Is it possible to maintain the answer for all the roots when adding a leaf to the tree?
    481 
    482 **Tutorial**
    483 
    484 Tutorial is loading...
    485 
    486 **Implementation**
    487 
    488 ```
    489 #include<bits/stdc++.h>
    490 using namespace std;
    491 #define int         long long
    492 #define pii         pair<int,int>
    493 #define all(v)      v.begin(),v.end()
    494 #define pb          push_back
    495 #define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
    496 #define over(x)     {cout<<(x)<<endl;return;}
    497 struct ds{
    498 	int seg[2000005],tag[2000005];
    499 	void build(int l,int r,int p){
    500 		seg[p]=(l==0? 0:1e18),tag[p]=0;
    501 		if(l==r)return;
    502 		int m=(l+r)>>1;
    503 		build(l,m,p*2+1);build(m+1,r,p*2+2);
    504 	}
    505 	void pushdown(int p){
    506 		if(!tag[p])return;
    507 		tag[p*2+1]+=tag[p];tag[p*2+2]+=tag[p];
    508 		seg[p*2+1]+=tag[p];seg[p*2+2]+=tag[p];
    509 		tag[p]=0;
    510 	}
    511 	void add(int l,int r,int s,int t,int p,int val){
    512 		if(l<=s&&t<=r){
    513 			seg[p]+=val;tag[p]+=val;
    514 			return;
    515 		}
    516 		int m=(s+t)>>1;pushdown(p);
    517 		if(m>=l)add(l,r,s,m,p*2+1,val);
    518 		if(m<r)add(l,r,m+1,t,p*2+2,val);
    519 		seg[p]=min(seg[p*2+1],seg[p*2+2]);
    520 	}
    521 	void update(int pos,int l,int r,int p,int val){
    522 		if(l==r){
    523 			seg[p]=val;
    524 			return;
    525 		}
    526 		int m=(l+r)>>1;pushdown(p);
    527 		if(m>=pos)update(pos,l,m,p*2+1,val);
    528 		else update(pos,m+1,r,p*2+2,val);
    529 		seg[p]=min(seg[p*2+1],seg[p*2+2]);
    530 	}
    531 }seg;
    532 int n;
    533 vector<int>v[500005];
    534 int fa[500005],an[500005][21];
    535 int dep[500005],dfn[500005],rev[500005];
    536 int tot,deg[500005],ls[500005];
    537 void dfs(int x,int pre,int d){
    538 	dep[x]=d;fa[x]=pre;an[x][0]=fa[x];ls[x]=1;
    539 	REP(i,0,__lg(n+1))if(an[x][i]==-1)an[x][i+1]=-1;else an[x][i+1]=an[an[x][i]][i];
    540 	rev[tot]=x;dfn[x]=tot++;
    541 	for(auto i:v[x])dfs(i,x,d+1),ls[x]+=ls[i];
    542 }
    543 int getlca(int x,int y){
    544 	if(dep[x]<dep[y])swap(x,y);
    545 	int d=dep[x]-dep[y];
    546 	for(int i=__lg(d);i>=0;--i)if((d>>i)&1)x=an[x][i];
    547 	if(x==y)return x;
    548 	d=dep[x];
    549 	for(int i=__lg(d);i>=0;--i)if((1<<i)<=dep[x]&&an[x][i]!=an[y][i])x=an[x][i],y=an[y][i];
    550 	return fa[x];
    551 }
    552 int getan(int x,int y){
    553 	if(dfn[y]>=dfn[x]&&dfn[y]<=ls[x]){
    554 		int d=dep[y]-dep[x]-1;
    555 		for(int i=0;(1<<i)<=d;++i)if((d>>i)&1)y=an[y][i];
    556 		return y;
    557 	}else return fa[x];
    558 }
    559 void updside(int x,int y){
    560 	if(dfn[y]>=dfn[x]&&dfn[y]<=ls[x]){
    561 		seg.add(0,n-1,0,n-1,0,1);
    562 		x=getan(x,y);
    563 		seg.add(dfn[x],ls[x],0,n-1,0,-1);
    564 	}else seg.add(dfn[x],ls[x],0,n-1,0,1);
    565 }
    566 int getdist(int x,int y){return dep[x]+dep[y]-2*dep[getlca(x,y)];}
    567 struct diameter{
    568 	int x,y,len;
    569 	int update(int z){
    570 		if(x==y){
    571 			int d=getdist(x,z);
    572 			if(d<=len)return d+len;
    573 			updside(y,z);
    574 			y=getan(y,z);
    575 			return d+len;
    576 		}else{
    577 			int d1=getdist(x,z),d2=getdist(y,z),d3=min(d1,d2);
    578 			if(d3<=len)return d3+len+1;
    579 			if(d1>d2)swap(x,y);
    580 			updside(y,z);
    581 			y=x;++len;return len*2;
    582 		}
    583 	}
    584 	int query(int z){
    585 		if(x==y)return len+getdist(x,z);
    586 		else return len+min(getdist(x,z),getdist(y,z))+1;
    587 	}
    588 };
    589 void Main() {
    590 	cin>>n;
    591 	REP(i,0,n)v[i].clear();
    592 	REP(i,1,n){
    593 		cin>>fa[i];--fa[i];
    594 		v[fa[i]].pb(i);
    595 	}
    596 	tot=0;dfs(0,-1,0);seg.build(0,n-1,0);
    597 	REP(i,0,n)deg[i]=0,ls[i]+=dfn[i]-1;
    598 	diameter d={0,0,0};
    599 	cout<<"1 ";
    600 	REP(i,1,n){
    601 		++deg[fa[i]];++deg[i];
    602 		if(deg[fa[i]]==4){
    603 			REP(j,i,n)cout<<-1<<' ';
    604 			cout<<endl;return;
    605 		}
    606 		if(deg[fa[i]]==3)seg.update(dfn[fa[i]],0,n-1,0,1e18);
    607 		seg.update(dfn[i],0,n-1,0,d.update(i));
    608 		cout<<seg.seg[0]+1<<' ';
    609 	}
    610 	cout<<endl;
    611 }
    612 void TC() {
    613     int tc=1;
    614     cin>>tc;
    615 	while(tc--){
    616 		Main();
    617 		cout.flush();
    618 	}
    619 }
    620 signed main() {
    621 	return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
    622 }
    623 /*
    624 1. CLEAR the arrays (ESPECIALLY multitests)
    625 2. DELETE useless output
    626  */
    627 ```
    628 
    629 [2006F - Dora's Paint](/contest/2006/problem/F "Codeforces Round 969 (Div. 1)")
    630 
    631 Here're two methods. Method $1$ is my method, and method $2$ is some testers' method.
    632 
    633 Method 1:
    634 
    635 **Hint1**
    636 
    637 Each column or row should be painted at most once. Suppose we paint each column and row exactly once. Then what does the number on one position tell us?
    638 
    639 **Answer**
    640 
    641 It tells us whether the row was painted first of the column was painted first. Try to build a graph.
    642 
    643 **Hint2**
    644 
    645 We can build a directed bipartite graph. How to judge whether it is possible to paint the graph? How to calculate the beauty of one single grid?
    646 
    647 **Answer**
    648 
    649 Do topological sort on the graph. A cycle means it is impossible. Otherwise, the topo sort splits the graph into several layers. The beauty is the product of factorials of number of nodes in the layers (except the first layer, for we needn't do those operations).
    650 
    651 **Hint3**
    652 
    653 How to solve the original problem when the initial grid has positive beauty? How to optimize? Consider adjacent layers.
    654 
    655 **Hint4**
    656 
    657 How to solve the original problem when the initial grid is impossible to be painted out? Are there too many ways to flip a block?
    658 
    659 **Hint5**
    660 
    661 How to optimize the process of building the graph and doing topological sort?
    662 
    663 **Tutorial**
    664 
    665 Tutorial is loading...
    666 
    667 **Implementation - method 1**
    668 
    669 ```
    670 #include<bits/stdc++.h>
    671 using namespace std;
    672 #define MOD         998244353
    673 #define speMOD      2933256077ll
    674 #define int         long long
    675 #define pii         pair<int,int>
    676 #define all(v)      v.begin(),v.end()
    677 #define pb          push_back
    678 #define REP(i,b,e)  for(int i=(b);i<(e);++i)
    679 #define over(x)     {cout<<x<<endl;return;}
    680 #define lowbit(x)   ((x)&(-(x)))
    681 #define cntbit(x)   __builtin_popcount(x)
    682 #define rf(v)       shuffle(all(v),sd);
    683 mt19937 sd(std::random_device{}());
    684 int qpow (int a,int b,int m=MOD,int res=1){
    685 	a%=m;
    686 	while(b>0)res=(b&1)?(res*a%m):(res),a=a*a%m,b>>=1;
    687 	return res;
    688 }
    689 int fac[2000005],inv[2000005],si[2000005];
    690 void init(int n){
    691 	fac[0]=inv[0]=si[0]=1;
    692 	REP(i,1,n+1)fac[i]=fac[i-1]*i%MOD;
    693 	inv[n]=qpow(fac[n],MOD-2);
    694 	for(int i=n-1;i>=1;--i)inv[i]=inv[i+1]*(i+1)%MOD;
    695 	REP(i,1,n+1)si[i]=inv[i]*fac[i-1]%MOD;
    696 }
    697 int binom(int x,int y){
    698 	return x<y||y<0? 0:fac[x]*inv[y]%MOD*inv[x-y]%MOD;
    699 }
    700 namespace fastIO {
    701 #define BUF_SIZE 6000010
    702     bool IOerror = 0;
    703     inline char nc() {
    704         static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
    705         if(p1 == pend) {
    706             p1 = buf;
    707             pend = buf + fread(buf, 1, BUF_SIZE, stdin);
    708             if(pend == p1) {
    709                 IOerror = 1;
    710                 return -1;
    711             }
    712         }
    713         return *p1++;
    714     }
    715     inline bool blank(char ch) {
    716         return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
    717     }
    718     inline void read(int &x) {
    719         char ch;
    720         while(blank(ch = nc()));
    721         if(IOerror)
    722             return;
    723         for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');
    724     }
    725 #undef BUF_SIZE
    726 };
    727 using namespace fastIO;
    728 int n,m;
    729 int a[200005],b[200005];
    730 vector<pii>c;
    731 int d1[200005],d2[200005];
    732 int visa[200005],visb[200005];
    733 vector<int>h[200005],nodes[200005],buc[200005];
    734 int X,Y;
    735 int id1[200005],id2[200005],cnt[400005];
    736 int solve(){
    737 	REP(i,0,n+1)buc[i].clear();
    738 	REP(i,0,n)buc[a[i]].pb(i);
    739 	int num=0;
    740 	REP(i,0,n+1)for(auto j:buc[i])id1[num++]=j;
    741 	REP(i,0,n+1)buc[i].clear();
    742 	REP(i,0,n)buc[b[i]].pb(i);
    743 	num=0;
    744 	REP(i,0,n+1)for(auto j:buc[i])id2[num++]=j;
    745 	REP(i,0,n)d1[i]=d2[i]=-1;
    746 	int ans=1,x=0,y=0,cur=0;
    747 	while(x<n||y<n){
    748 		if(x<n&&a[id1[x]]<=y){
    749 			int sum=0;
    750 			while(x<n&&a[id1[x]]<=y)++sum,d1[id1[x++]]=cur;
    751 			if(cur)(ans*=fac[sum])%=MOD;
    752 		}else if(y<n&&b[id2[y]]<=x){
    753 			int sum=0;
    754 			while(y<n&&b[id2[y]]<=x)++sum,d2[id2[y++]]=cur;
    755 			if(cur)(ans*=fac[sum])%=MOD;
    756 		}else return X=x,Y=y,0;
    757 		++cur;
    758 	}
    759 	return ans;
    760 }
    761 int updater(int x,int y){
    762 	int f=0,ret;
    763 	for(auto i:c)if(i==make_pair(x,y))f=1;
    764 	if(f)--b[y],++a[x],ret=solve(),++b[y],--a[x];
    765 	else ++b[y],--a[x],ret=solve(),--b[y],++a[x];
    766 	return ret;
    767 }
    768 void Main() {
    769 	fastIO::read(n);fastIO::read(m);
    770 	c.clear();
    771 	REP(i,0,n)a[i]=b[i]=0;
    772 	REP(i,0,n*2+2)cnt[i]=0;
    773 	REP(i,0,n)visa[i]=visb[i]=0,h[i].clear(),nodes[i].clear();
    774 	REP(i,0,m){
    775 		int x,y;
    776 		fastIO::read(x);fastIO::read(y);
    777 		--x,--y;
    778 		c.pb({x,y});
    779 		++b[y];--a[x];
    780 	}
    781 	REP(i,0,n)a[i]+=n;
    782 	int ans=solve();
    783 	if(!ans){
    784 		if(X==n-1||Y==n-1)over(0)
    785 		int x=id1[X],y=id2[Y],f=0;
    786 		for(auto i:c)if(i==make_pair(x,y)){f=1;break;}
    787 		if(f){
    788 			for(auto i:c)if(i.first==x)visb[i.second]=1;
    789 			for(auto i:c)if(i.second==y)visa[i.first]=1;
    790 			X=Y=-1;
    791 			for(auto i:c)if(i.first!=x&&i.second!=y){
    792 				if(!visa[i.first]&&!visb[i.second]){X=i.first,Y=i.second;break;}
    793 			}
    794 			if(X==-1)over(0);
    795 		}else{
    796 			X=Y=-1;
    797 			for(auto i:c)h[i.first].pb(i.second);
    798 			int sum=0;
    799 			for(auto i:h[x])visa[i]=1,++sum;
    800 			REP(i,0,n){
    801 				int found=0;
    802 				for(auto j:h[i])if(j==y){found=1;break;}
    803 				if(!found)continue;
    804 				vector<int>z;
    805 				for(auto j:h[i])if(visa[j])visa[j]=0,--sum,z.pb(j);
    806 				if(sum){
    807 					X=i;
    808 					REP(j,0,n)if(visa[j])Y=j;
    809 					break;
    810 				}
    811 				for(auto j:z)++sum,visa[j]=1;
    812 			}
    813 			if(X==-1)over(0);
    814 		}
    815 		int x2=X,y2=Y;
    816 		int ans=updater(x,y)+updater(x,y2)+updater(x2,y)+updater(x2,y2);
    817 		cout<<(ans%MOD*qpow(n*n%MOD,MOD-2))%MOD<<endl;
    818 		return;
    819 	}
    820 	REP(i,0,n)++cnt[d1[i]],++cnt[d2[i]];
    821 	int res=0;
    822 	(res+=ans*cnt[0]%MOD*(cnt[1]==1? cnt[2]+1:1))%=MOD;
    823 	if(cnt[2]&&cnt[1])(res+=ans*(cnt[2]==1? cnt[3]+1:1))%=MOD;
    824 	REP(i,2,2*n-1)if(cnt[i]&&cnt[i+1]){
    825 		(res+=ans*(cnt[i+1]==1? cnt[i+2]+1:1)%MOD*(cnt[i]==1? cnt[i-1]+1:1))%=MOD;
    826 	}
    827 	cout<<res*qpow(n*n%MOD,MOD-2)%MOD<<endl;
    828 }
    829 void TC() {
    830 	init(1000000);
    831 	int tc=1;
    832 	fastIO::read(tc);
    833 	while(tc--) {
    834 		Main();
    835 		cout.flush();
    836 	}
    837 }
    838 signed main() {
    839 	return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
    840 }
    841 /*
    842 1. CLEAR the arrays (ESPECIALLY multitests)
    843 2. DELETE useless output
    844  */
    845 ```
    846 
    847 Method 2:
    848 
    849 **Hint1**
    850 
    851 Try to find some way to "sort" the grid, for swapping different rows and different columns doesn't matter. How?
    852 
    853 **Answer**
    854 
    855 Sort by the number of $1$.
    856 
    857 **Hint2**
    858 
    859 How to calculate the beauty?
    860 
    861 **Answer**
    862 
    863 The beauty is the product of factorials of number of equal rows and equal columns.
    864 
    865 **Hint3**
    866 
    867 How to solve the original problem when the initial grid has positive beauty? How to optimize?
    868 
    869 **Hint4**
    870 
    871 How to solve the original problem when the initial grid is impossible to be painted out? Are there too many ways to flip a block?
    872 
    873 **Tutorial**
    874 
    875 Read the hints.
    876 
    877 Let's sort the rows and columns in some way, which means you should swap two rows or two columns each time to make them ordered. Let's sort by the number of $1$ in each row and column. For example, the result of sorting the left part is shown in the right part:
    878 
    879 $ \left[\begin{matrix}2&1&1&1\\2&2&1&2\\1&1&1&1\\2&2&1&2\end{matrix}\right]\Rightarrow\left[\begin{matrix}1&1&1&1\\1&1&1&2\\1&2&2&2\\1&2&2&2\end{matrix}\right] $
    880 
    881 We claim that the grid is solvealbe if and only if the later rows are "included" by previous rows, and so for the columns. For example, if a position in any row is filled with $1$, then the position in any previous row must also be $1$. This is correct because you'll notice that any submatrices of the following two types cannot appear in a solveable grid. To check that, you'll only need to check adjacent rows and columns.
    882 
    883 $\left[\begin{matrix}1&2\\2&1\end{matrix}\right],\left[\begin{matrix}2&1\\1&2\end{matrix}\right]$
    884 
    885 After you sort all of that, the number of ways to paint it is easy to think about. It's similar to the product of factorials of the number of each kind of rows(for example, the last two rows in the right above). The only to notice is the first step of painting shouldn't be counted.
    886 
    887 Consider modifying one block. If the initial grid is solveable, there're only $O(n)$ types of changing(in each row, all the $1$ and $2$ can be considered the same). Each type of changing can be done in $O(1)$ using simple discussion.
    888 
    889 If the initial grid is unsolveable, we should find the two adjacent rows **and** columns that starts the problem. We claim that the block to change must belong to one of the four blocks in the intersection of the rows and columns. Just try every possible situation and do brute force on it.
    890 
    891 For example, consider the following matrix: The first two columns and the last two rows went wrong. So let's try to change blocks $(3,1),(3,2),(4,1),(4,2)$ to judge whether it is possible.
    892 
    893 $\left[\begin{matrix}1&1&1&1\\1&1&1&2\\1&2&2&2\\2&1&2&2\end{matrix}\right]$
    894 
    895 The time complexity is $O((n+m)\log n)$, and if you implement carefully enough you can solve it in $O(n+m)$.
    896 
    897 **Implementation - method 2**
    898 
    899 ```
    900 #if defined(LOCAL) or not defined(LUOGU)
    901 #pragma GCC optimize(3)
    902 #pragma GCC optimize("Ofast,unroll-loops")
    903 #endif
    904 #include<bits/stdc++.h>
    905 using namespace std;
    906 struct time_helper
    907 {
    908 #ifdef LOCAL
    909 	clock_t time_last;
    910 #endif
    911 	time_helper()
    912 	{
    913 #ifdef LOCAL
    914 		time_last=clock();
    915 #endif
    916 	}
    917 	void test()
    918 	{
    919 #ifdef LOCAL
    920 		auto time_now=clock();
    921 		std::cerr<<"time:"<<1.*(time_now-time_last)/CLOCKS_PER_SEC<<";all_time:"<<1.*time_now/CLOCKS_PER_SEC<<std::endl;
    922 		time_last=time_now;
    923 #endif
    924 	}
    925 	~time_helper()
    926 	{
    927 		test();
    928 	}
    929 }time_helper;
    930 #ifdef LOCAL
    931 #include"dbg.h"
    932 #else
    933 #define dbg(...) (__VA_ARGS__)
    934 #endif
    935 namespace Fread{const int SIZE=1<<16;char buf[SIZE],*S,*T;inline char getchar(){if(S==T){T=(S=buf)+fread(buf,1,SIZE,stdin);if(S==T)return'\n';}return *S++;}}namespace Fwrite{const int SIZE=1<<16;char buf[SIZE],*S=buf,*T=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}inline void putchar(char c){*S++=c;if(S==T)flush();}struct NTR{~NTR(){flush();}}ztr;}
    936 #define getchar Fread::getchar
    937 #define putchar Fwrite::putchar
    938 #define Setprecision 10
    939 #define between '\n'
    940 #define __int128 long long
    941 template<typename T>struct is_char{static constexpr bool value=(std::is_same<T,char>::value||std::is_same<T,signed char>::value||std::is_same<T,unsigned char>::value);};template<typename T>struct is_integral_ex{static constexpr bool value=(std::is_integral<T>::value||std::is_same<T,__int128>::value)&&!is_char<T>::value;};template<typename T>struct is_floating_point_ex{static constexpr bool value=std::is_floating_point<T>::value||std::is_same<T,__float128>::value;};namespace Fastio{struct Reader{template<typename T>typename std::enable_if_t<std::is_class<T>::value,Reader&>operator>>(T&x){for(auto &y:x)*this>>y;return *this;}template<typename T>typename std::enable_if_t<is_integral_ex<T>::value,Reader&>operator>>(T&x){char c=getchar();short f=1;while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}x=0;while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x*=f;return *this;}template<typename T>typename std::enable_if_t<is_floating_point_ex<T>::value,Reader&>operator>>(T&x){char c=getchar();short f=1,s=0;x=0;T t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}template<typename T>typename std::enable_if_t<is_char<T>::value,Reader&>operator>>(T&c){c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();return *this;}Reader&operator>>(char*str){int len=0;char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return*this;}Reader&operator>>(std::string&str){str.clear();char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str.push_back(c),c=getchar();return*this;}Reader(){}}cin;const char endl='\n';struct Writer{typedef __int128 mxdouble;template<typename T>typename std::enable_if_t<std::is_class<T>::value,Writer&>operator<<(T x){for(auto &y:x)*this<<y<<between;*this<<'\n';return *this;}template<typename T>typename std::enable_if_t<is_integral_ex<T>::value,Writer&>operator<<(T x){if(x==0)return putchar('0'),*this;if(x<0)putchar('-'),x=-x;static int sta[45];int top=0;while(x)sta[++top]=x%10,x/=10;while(top)putchar(sta[top]+'0'),--top;return*this;}template<typename T>typename std::enable_if_t<is_floating_point_ex<T>::value,Writer&>operator<<(T x){if(x<0)putchar('-'),x=-x;x+=pow(10,-Setprecision)/2;mxdouble _=x;x-=(T)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}template<typename T>typename std::enable_if_t<is_char<T>::value,Writer&>operator<<(T c){putchar(c);return*this;}Writer&operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(std::string str){int st=0,ed=str.size();while(st<ed)putchar(str[st++]);return*this;}Writer(){}}cout;}
    942 #define cin Fastio::cin
    943 #define cout Fastio::cout
    944 #define endl Fastio::endl
    945  
    946 void solve();
    947 main()
    948 {
    949 	int t=1;
    950 	cin>>t;
    951 	while(t--)solve();
    952 }
    953 template <uint32_t mod>
    954 struct LazyMontgomeryModInt {
    955 	using mint = LazyMontgomeryModInt;
    956 	using i32 = int32_t;
    957 	using u32 = uint32_t;
    958 	using u64 = uint64_t;
    959 	static constexpr u32 get_r() {
    960 		u32 ret = mod;
    961 		for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret;
    962 		return ret;
    963 	}
    964 	static constexpr u32 r = get_r();
    965 	static constexpr u32 n2 = -u64(mod) % mod;
    966 	static_assert(r * mod == 1, "invalid, r * mod != 1");
    967 	static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30");
    968 	static_assert((mod & 1) == 1, "invalid, mod % 2 == 0");
    969 	u32 a;
    970 	constexpr LazyMontgomeryModInt() : a(0) {}
    971 	constexpr LazyMontgomeryModInt(const int64_t &b)
    972 			: a(reduce(u64(b % mod + mod) * n2)){};
    973 	static constexpr u32 reduce(const u64 &b) {
    974 		return (b + u64(u32(b) * u32(-r)) * mod) >> 32;
    975 	}
    976 	constexpr mint &operator+=(const mint &b) {
    977 		if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod;
    978 		return *this;
    979 	}
    980 	constexpr mint &operator-=(const mint &b) {
    981 		if (i32(a -= b.a) < 0) a += 2 * mod;
    982 		return *this;
    983 	}
    984 	constexpr mint &operator*=(const mint &b) {
    985 		a = reduce(u64(a) * b.a);
    986 		return *this;
    987 	}
    988 	constexpr mint &operator/=(const mint &b) {
    989 		*this *= b.inverse();
    990 		return *this;
    991 	}
    992 	constexpr mint operator+(const mint &b) const { return mint(*this) += b; }
    993 	constexpr mint operator-(const mint &b) const { return mint(*this) -= b; }
    994 	constexpr mint operator*(const mint &b) const { return mint(*this) *= b; }
    995 	constexpr mint operator/(const mint &b) const { return mint(*this) /= b; }
    996 	constexpr bool operator==(const mint &b) const {
    997 		return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a);
    998 	}
    999 	constexpr bool operator!=(const mint &b) const {
   1000 		return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a);
   1001 	}
   1002 	constexpr mint operator-() const { return mint() - mint(*this); }
   1003 	constexpr mint pow(u64 n) const {
   1004 		mint ret(1), mul(*this);
   1005 		while (n > 0) {
   1006 			if (n & 1) ret *= mul;
   1007 			mul *= mul;
   1008 			n >>= 1;
   1009 		}
   1010 		return ret;
   1011 	}
   1012 	constexpr mint inverse() const { return pow(mod - 2); }
   1013 	friend ostream &operator<<(ostream &os, const mint &b) {
   1014 		return os << b.get();
   1015 	}
   1016 	friend istream &operator>>(istream &is, mint &b) {
   1017 		int64_t t;
   1018 		is >> t;
   1019 		b = LazyMontgomeryModInt<mod>(t);
   1020 		return (is);
   1021 	}
   1022 	constexpr u32 get() const {
   1023 		u32 ret = reduce(a);
   1024 		return ret >= mod ? ret - mod : ret;
   1025 	}
   1026 	static constexpr u32 get_mod() { return mod; }
   1027 	explicit operator u32() const {return get();}
   1028 };
   1029 #define modint LazyMontgomeryModInt
   1030 #define mint modint<p>
   1031 constexpr int p=998244353;
   1032 std::pmr::monotonic_buffer_resource pool(100000000);
   1033 void solve()
   1034 {
   1035 	int n,m;
   1036 	cin>>n>>m;
   1037 	vector<std::pmr::vector<int>>a(n,std::pmr::vector<int>{&pool});
   1038 	time_helper.test();
   1039 	while(m--)
   1040 	{
   1041 		int u,v;
   1042 		cin>>u>>v;
   1043 		u--,v--;
   1044 		a[u].emplace_back(v);
   1045 	}
   1046 	time_helper.test();
   1047 	std::pmr::vector<mint>inv{&pool},fac{&pool},ifac{&pool};
   1048 	inv.resize(n+1),fac.resize(n+1),ifac.resize(n+1);
   1049 	std::pmr::vector<int>arr_cnt{&pool};
   1050 	arr_cnt.resize(n+2);
   1051 	auto arr_sort=[&](const auto&a)
   1052 	{
   1053 		for(int i=0;i<n;i++)
   1054 		arr_cnt[a[i].size()+1]++;
   1055 		for(int x=1;x<=n;x++)
   1056 		arr_cnt[x]+=arr_cnt[x-1];
   1057 		vector<std::pmr::vector<int>>b(n,std::pmr::vector<int>{&pool});
   1058 		for(int i=0;i<n;i++)
   1059 		b[arr_cnt[a[i].size()]++]=move(a[i]);
   1060 		for(int x=0;x<=n+1;x++)
   1061 		arr_cnt[x]=0;
   1062 		return b;
   1063 	};
   1064 	a=move(arr_sort(a));
   1065 	auto arr_eq=[&](const auto&a,const auto&b)
   1066 	{
   1067 		if(a.size()!=b.size())return false;
   1068 		bool res=1;
   1069 		for(auto q:a)arr_cnt[q]=1;
   1070 		for(auto q:b)if(!arr_cnt[q]){res=0;break;}
   1071 		for(auto q:a)arr_cnt[q]=0;
   1072 		return res;
   1073 	};
   1074 	auto arr_includes=[&](const auto&a,const auto&b)
   1075 	{
   1076 		bool res=1;
   1077 		for(auto q:a)arr_cnt[q]=1;
   1078 		for(auto q:b)if(!arr_cnt[q]){res=0;break;}
   1079 		for(auto q:a)arr_cnt[q]=0;
   1080 		return res;
   1081 	};
   1082 	auto arr_set_difference=[&](const auto&a,const auto&b,auto &diff)
   1083 	{
   1084 		for(auto q:b)arr_cnt[q]=1;
   1085 		for(auto q:a)
   1086 		if(!arr_cnt[q])
   1087 		{
   1088 			diff.emplace_back(q);
   1089 			if(diff.size()>2)break;
   1090 		}
   1091 		for(auto q:b)arr_cnt[q]=0;
   1092 	};
   1093 	{
   1094 		fac[0]=1;
   1095 		for(int x=1;x<=n;x++)
   1096 		fac[x]=fac[x-1]*x;
   1097 		ifac[n]=fac[n].inverse();
   1098 		for(int x=n;x>=1;x--)
   1099 		ifac[x-1]=ifac[x]*x,inv[x]=ifac[x]*fac[x-1];
   1100 	}
   1101 	int failcnt=0;
   1102 	for(int x=1;x<n;x++)
   1103 	failcnt+=!(arr_includes(a[x],a[x-1]));
   1104 	if(failcnt==0)
   1105 	{
   1106 		int nc=0;
   1107 		mint ansbas=fac[a[0].size()],ans=0;
   1108 		std::pmr::vector<int>tnc{&pool},tmc{&pool};
   1109 		tmc.emplace_back(a[0].size());
   1110 		int ct=0;
   1111 		for(int x=0;x<n;x++)
   1112 		if(x==n-1||!arr_eq(a[x],a[x+1]))
   1113 		{
   1114 			nc++;
   1115 			if(a[x].size()!=n)
   1116 			ansbas*=fac[nc];
   1117 			int mc=0;
   1118 			if(x==n-1)mc=n-a[x].size();
   1119 			else mc=a[x+1].size()-a[x].size();
   1120 			if(x!=n-1)
   1121 			ansbas*=fac[mc];
   1122 			tnc.emplace_back(nc);
   1123 			tmc.emplace_back(mc);
   1124 			nc=0;
   1125 			ct++;
   1126 		}
   1127 		else nc++;
   1128 		for(int x=0;x<ct;x++)
   1129 		{
   1130 			int nc=tnc[x],mc=tmc[x+1];
   1131 			if(mc==0)continue;
   1132 			mint fix=ansbas;
   1133 			if(x==ct-1)
   1134 			{
   1135 				fix*=mc;
   1136 			}
   1137 			if(x==ct-2&&mc==1&&tmc[x+2]==0)
   1138 			{
   1139 				fix*=inv[tnc[x+1]+1];
   1140 			}
   1141 			if(x==ct-1||mc!=1)
   1142 			{
   1143 				if(mc)
   1144 				{
   1145 					if(nc>1)ans+=fix;
   1146 					else ans+=fix*(tmc[x]+1);
   1147 				}
   1148 			}
   1149 			else if(nc>1)ans+=fix*(tnc[x+1]+1);
   1150 			else ans+=fix*(tnc[x+1]+1)*(tmc[x]+1);
   1151 		}
   1152 		for(int x=0;x<ct;x++)
   1153 		{
   1154 			int nc=tnc[x],mc=tmc[x];
   1155 			if(mc==0)continue;
   1156 			mint fix=ansbas;
   1157 			if(x==ct-1)
   1158 			{
   1159 			    if(tmc[x+1]==0)fix*=nc;
   1160 			    if(nc==1)fix*=inv[tmc[x+1]+1];
   1161 			}
   1162 			if(x==0||mc!=1)
   1163 			{
   1164 				if(mc)
   1165 				{
   1166 					if(nc>1)ans+=fix;
   1167 					else ans+=fix*(tmc[x+1]+1);
   1168 				}
   1169 			}
   1170 			else if(nc>1)ans+=fix*(tnc[x-1]+1);
   1171 			else ans+=fix*(tnc[x-1]+1)*(tmc[x+1]+1);
   1172 		}
   1173 		cout<<(ans*inv[n]*inv[n]).get()<<endl;
   1174 		return;
   1175 	}
   1176 	if(failcnt>2){cout<<0<<endl;return;}
   1177 	mint ans=0;
   1178     auto calc=[&](vector<std::pmr::vector<int>>&a)->mint
   1179 	{
   1180         a=move(arr_sort(a));
   1181 		for(int x=1;x<n;x++)
   1182 		if(!arr_includes(a[x],a[x-1]))return 0;
   1183 		int nc=0;
   1184 		mint ansbas=fac[a[0].size()];
   1185 		for(int x=0;x<n;x++)
   1186 		if(x==n-1||!arr_eq(a[x],a[x+1]))
   1187 		{
   1188 			nc++;
   1189 			if(a[x].size()!=n)
   1190 			ansbas=ansbas*fac[nc];
   1191 			int mc=0;
   1192 			if(x==n-1)mc=n-a[x].size();
   1193 			else mc=a[x+1].size()-a[x].size();
   1194 			if(x!=n-1)
   1195 			ansbas=ansbas*fac[mc];
   1196 			nc=0;
   1197 		}
   1198 		else nc++;
   1199 		return ansbas;
   1200 	};
   1201 	std::pmr::set<pair<int,int>>st{&pool};
   1202 	std::pmr::vector<int>diff{&pool};
   1203 	vector<std::pmr::vector<int>>b(n,std::pmr::vector<int>{&pool});
   1204 	time_helper.test();
   1205 	for(int x=1;x<n;x++)
   1206 	if(!arr_includes(a[x],a[x-1]))
   1207 	{
   1208 		for(int y=x+2;y<n;y++)
   1209 		if(!arr_includes(a[y],a[y-1]))goto fail;
   1210 		{
   1211 			diff.clear();
   1212 			arr_set_difference(a[x],a[x-1],diff);
   1213 			if(diff.size()<=1)
   1214 			{
   1215 				if(!st.count({x-1,diff[0]}))
   1216 				{
   1217 					b=a;
   1218 					b[x-1].emplace_back(diff[0]);
   1219 					ans+=calc(b),st.insert({x-1,diff[0]});
   1220 				}
   1221 				if(!st.count({x,diff[0]}))
   1222 				{
   1223 					b=a;
   1224 					b[x].erase(find(b[x].begin(),b[x].end(),diff[0]));
   1225 					ans+=calc(b),st.insert({x,diff[0]});
   1226 				}
   1227 			}
   1228 		}
   1229 		{
   1230 			diff.clear();
   1231 			arr_set_difference(a[x-1],a[x],diff);
   1232 			if(diff.size()<=1)
   1233 			{
   1234 				if(!st.count({x,diff[0]}))
   1235 				{
   1236 					b=a;
   1237 					b[x].emplace_back(diff[0]);
   1238 					ans+=calc(b),st.insert({x,diff[0]});
   1239 				}
   1240 				if(!st.count({x-1,diff[0]}))
   1241 				{
   1242 					b=a;
   1243 					b[x-1].erase(find(b[x-1].begin(),b[x-1].end(),diff[0]));
   1244 					ans+=calc(b),st.insert({x-1,diff[0]});
   1245 				}
   1246 			}
   1247 		}
   1248 		fail:
   1249 		break;
   1250 	}
   1251 	cout<<(ans*inv[n]*inv[n]).get()<<endl;
   1252 }
   1253 ```