codeforces-scrape

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

2063.md (20587B)


      1 Source: https://codeforces.com/blog/entry/138593
      2 
      3 **Rating Predictions**
      4 
      5 | Handles | A | B | C | D | E | F1 | F2 |
      6 | --- | --- | --- | --- | --- | --- | --- | --- |
      7 | [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") | 800 | 1000 | 1500 | 2200 | 2400 | 1800 | 2600 |
      8 | [chromate00](/profile/chromate00 "Expert chromate00") | 800 | 1100 | 1500 | 2100 | 2300 | 1800 | 2700 |
      9 | [redpanda](/profile/redpanda "Expert redpanda") | 800 | 900 | 1400 | 2000 | 2400 |  |  |
     10 | [larush](/profile/larush "Expert larush") | 800 | 1100 | 1600 | 2100 |  |  |  |
     11 | [FairyWinx](/profile/FairyWinx "Grandmaster FairyWinx") | 800 | 900 | 1500 | 2000 | 2400 | 1800 | 2500 |
     12 | [priyanshu.p](/profile/priyanshu.p "Master priyanshu.p") | 800 | 1200 | 1500 | 2000 | 2500 | 2000 |  |
     13 | [Intellegent](/profile/Intellegent "Master Intellegent") | 800 | 1000 | 1400 | 2000 | 2200 | 2000 | 2600 |
     14 | [redheadphone](/profile/redheadphone "Candidate Master redheadphone") | 800 | 1200 | 1400 | 2000 |  |  |  |
     15 | [beaten_by_ai](/profile/beaten_by_ai "Expert beaten_by_ai") | 800 | 1100 | 1500 | 2100 | 2100 | 2000 | 2500 |
     16 | [Mukundan314](/profile/Mukundan314 "Candidate Master Mukundan314") | 800 | 1000 | 1600 | 2000 | 2300 | 1900 | 2400 |
     17 | [Think_Only_Once](/profile/Think_Only_Once "Expert Think_Only_Once") | 800 | 1000 | 1500 | 1900 | 2200 | 1900 | 2400 |
     18 | [ProofByContradiction_](/profile/ProofByContradiction_ "Expert ProofByContradiction_") | 800 | 1100 | 1500 | 2000 | 2300 |  |  |
     19 | [-firefly-](/profile/-firefly- "Master -firefly-") | 800 | 1100 | 1500 | 1900 | 2400 | 1800 | 2500 |
     20 | [temporary1](/profile/temporary1 "Master temporary1") | 800 | 1000 | 1500 | 2100 | 2300 | 2000 | 2600 |
     21 | [cry](/profile/cry "International Master cry") | 800 | 1200 | 1400 | 2100 | 2300 |  |  |
     22 |  |  |  |  |  |  |  |  |
     23 | **Average** | 800 | 1060 | 1486.67 | 2033.33 | 2315.38 | 1900 | 2533.33 |
     24 | **Average (Round)** | 800 | 1100 | 1500 | 2000 | 2300 | 1900 | 2500 |
     25 | **Median** | 800 | 1100 | 1500 | 2000 | 2300 | 1900 | 2500 |
     26 
     27 The editorial for each task is written by me, [chromate00](/profile/chromate00 "Expert chromate00"). I tried to explain each task with as much detail I could fit in. Brace yourselves, it is going to be LONG. Please don't try to open all spoilers at once, it lagged my browser. Also, I apologize for not telling you strongly enough to read every problem, almost every tester thought F1 is easy if you read it well...
     28 
     29 Also, our fellow [wuhudsm](/profile/wuhudsm "Master wuhudsm") told me there will be another community contest in the Gym soon, details will be posted on <https://codeforces.com/blog/entry/138706> shortly :catThink:
     30 
     31 **UPD**: Added solution codes to all solutions.
     32 
     33 ---
     34 
     35 ## [2063A - Minimal Coprime](/contest/2063/problem/A "Codeforces Round 1000 (Div. 2)")
     36 
     37 Author: [chromate00](/profile/chromate00 "Expert chromate00")
     38 
     39 **Hint**
     40 
     41 Well, we gave you enough hints in the examples. I believe you can already guess it.
     42 
     43 **Editorial**
     44 
     45 Tutorial is loading...
     46 
     47 **Code (Python)**
     48 
     49 ```
     50 for i in range(int(input())):
     51     x,y=map(int,input().split())
     52     if x==y==1:
     53         print(1)
     54     else:
     55         print(y-x)
     56 ```
     57 
     58 ## [2063B - Subsequence Update](/contest/2063/problem/B "Codeforces Round 1000 (Div. 2)")
     59 
     60 Author: [Think_Only_Once](/profile/Think_Only_Once "Expert Think_Only_Once")
     61 
     62 **Hint**
     63 
     64 Assume that you chose some two indices $i$ and $j$ included in the subsequence, such that $i \lt l$ and $j \gt r$. Does this actually help decrease the answer in any way?
     65 
     66 **Editorial**
     67 
     68 Tutorial is loading...
     69 
     70 **Code (Python)**
     71 
     72 ```
     73 import sys
     74 input=lambda:sys.stdin.readline().rstrip()
     75  
     76 for _ in range(int(input())):
     77     n,l,r=map(int,input().split());l-=1
     78     arr=[*map(int,input().split())]
     79     brr=arr[:l]+sorted(arr[l:])
     80     crr=sorted(arr[:r])[::-1]+arr[r:]
     81     print(min(sum(brr[l:r]),sum(crr[l:r])))
     82 ```
     83 
     84 ## [2063C - Remove Exactly Two](/contest/2063/problem/C "Codeforces Round 1000 (Div. 2)")
     85 
     86 Author: [chromate00](/profile/chromate00 "Expert chromate00")
     87 
     88 **Hint**
     89 
     90 The answer after choosing two vertices is decided by the degrees of the two vertices, **and whether the two vertices are adjacent**. Can you find a clean solution where you don't have to care about the latter?
     91 
     92 **Big Hint**
     93 
     94 Sure, you can do DP on tree, but that's not what we want you to use. Think easier.
     95 
     96 **Editorial**
     97 
     98 Tutorial is loading...
     99 
    100 **Code (Python, Approach 1)**
    101 
    102 ```
    103 import sys
    104 input=lambda:sys.stdin.readline().rstrip()
    105 for i in range(int(input())):
    106     n=int(input())
    107     deg=[0]*n
    108     adj=[[] for i in range(n)]
    109     for i in range(n-1):
    110         u,v=map(int,input().split())
    111         u-=1;v-=1
    112         deg[u]+=1
    113         deg[v]+=1
    114         adj[u].append(v)
    115         adj[v].append(u)
    116     ans=1
    117     mans=0
    118     sdeg=sorted(deg)
    119     for i in range(n):
    120         ans=deg[i]
    121         ideg=[]
    122         for v in adj[i]:
    123             ideg.append(deg[v])
    124         ideg.append(deg[i])
    125         ideg.sort(reverse=True)
    126         rem=[]
    127         mx=-1
    128         for d in ideg:
    129             if sdeg[-1]==d:
    130                 sdeg.pop()
    131                 rem.append(d)
    132         rem.reverse()
    133         if sdeg:
    134             mx=max(mx,sdeg[-1])
    135         for v in adj[i]:
    136             mx=max(mx,deg[v]-1)
    137         for d in rem:
    138             sdeg.append(d)
    139         mans=max(ans+mx-1,mans)
    140     print(mans)
    141 ```
    142 
    143 ## [2063D - Game With Triangles](/contest/2063/problem/D "Codeforces Round 1000 (Div. 2)")
    144 
    145 Author: [wuhudsm](/profile/wuhudsm "Master wuhudsm") (Original Idea) & [chromate00](/profile/chromate00 "Expert chromate00") (Modified Idea)
    146 
    147 **Hint**
    148 
    149 The maximum score $g(x_a,x_b)$ after performing $x_a$ times with two points on $y=0$, and $x_b$ times with two points on $y=2$, can be easily computed in $\mathcal{O}(1)$ time. But naively checking all possible number of operations takes $\mathcal{O}(nm)$ time. Is there a property we can abuse so that we can solve for each $k$ faster?
    150 
    151 **Big Hint**
    152 
    153 $g(x_a,x_b)$ is a function consisting of two prefix sums, each for a **strictly decreasing** sequence.
    154 
    155 **Editorial**
    156 
    157 Tutorial is loading...
    158 
    159 **Code (C++)**
    160 
    161 ```
    162 #include<bits/stdc++.h>
    163 using namespace std;
    164 using ll=long long;
    165  
    166 int main()
    167 {
    168   cin.tie(0)->sync_with_stdio(0);
    169   int t;cin>>t;
    170   while(t--)
    171   {
    172     int n,m;cin>>n>>m;
    173     vector<ll>arr(n),brr(m);
    174     for(ll&i:arr)cin>>i;
    175     for(ll&i:brr)cin>>i;
    176     sort(begin(arr),end(arr));
    177     sort(begin(brr),end(brr));
    178     vector<ll>asum(n+2),bsum(m+2);
    179     for(int i=1;i<=n;i++)asum[i]=asum[i-1]+(arr[n-i]-arr[i-1]);
    180     for(int i=1;i<=m;i++)bsum[i]=bsum[i-1]+(brr[m-i]-brr[i-1]);
    181     vector<ll>ans{0};
    182     // maximize asum[ka]+bsum[kb]
    183     // s.t. ka+kb = x
    184     //      ka*2+kb <= n -> ka*2+(x-ka) <= n -> ka+x <= n   -> ka <= n-x
    185     //      ka+kb*2 <= m -> ka+2*(x-ka) <= m -> 2*x-ka <= m -> ka >= 2*x-m
    186     //      ka >= 0, x-ka >= 0
    187     for(int x=1;2*x-m<=n-x;x++)
    188     {
    189       ll L=max(0,2*x-m),R=min(x,n-x);
    190       if(L>R)break;
    191       auto f=[&](int ka){return asum[ka]+bsum[x-ka];};
    192       while(R-L>3)
    193       {
    194         ll mL=(L*2+R)/3,mR=(L+R*2)/3;
    195         if(f(mL)>f(mR))R=mR;
    196         else L=mL;
    197       }
    198       ll mans=0;
    199       for(int i=L;i<=R;i++)
    200       {
    201         mans=max(mans,f(i));
    202       }
    203       ans.push_back(mans);
    204     }
    205     int kmax=(int)size(ans)-1;
    206     cout<<kmax<<"\n";
    207     for(int i=1;i<=kmax;i++)cout<<ans[i]<<" \n"[i==kmax];
    208   }
    209 }
    210 ```
    211 
    212 ## [2063E - Triangle Tree](/contest/2063/problem/E "Codeforces Round 1000 (Div. 2)")
    213 
    214 Author: [Think_Only_Once](/profile/Think_Only_Once "Expert Think_Only_Once")
    215 
    216 **Hint**
    217 
    218 When $(u,v)$ is a good pair, $f(u,v)$ is actually simply represented as follows.
    219 
    220 $f(u,v)=2 \cdot \min(\text{dist}(u,\text{lca}),\text{dist}(v,\text{lca}))-1$
    221 
    222 Naively calculating this for all good pairs takes $\mathcal{O}(n^2)$ time. Can you find a different representation where we can count wiser?
    223 
    224 **Editorial**
    225 
    226 Tutorial is loading...
    227 
    228 **Code (C++)**
    229 
    230 ```
    231 #include<bits/stdc++.h>
    232 using namespace std;
    233 using ll=long long;
    234 
    235 int main()
    236 {
    237     cin.tie(0)->sync_with_stdio(0);
    238     int t;cin>>t;
    239     while(t--)
    240     {
    241         ll n;cin>>n;
    242         vector<ll>d(n,0),s(n),dc(n),dcs;
    243         vector<vector<ll>>adj(n);
    244         for(int i=1;i<n;i++)
    245         {
    246             int u,v;cin>>u>>v;
    247             u--;v--;
    248             adj[u].push_back(v);
    249             adj[v].push_back(u);
    250         }
    251         auto dfs1=[&](auto dfs1,int v,int p=-1)->void
    252         {
    253             dc[d[v]]++;
    254             ll sz=1;
    255             for(int w:adj[v])if(w!=p)
    256             {
    257                 d[w]=d[v]+1;
    258                 dfs1(dfs1,w,v);
    259                 sz+=s[w];
    260             }
    261             s[v]=sz;
    262         };
    263         dfs1(dfs1,0);
    264         dcs=dc;
    265         for(int i=n-2;i>=0;i--)dcs[i]+=dcs[i+1];
    266         ll ans=0,ans2=0;
    267         auto dfs2=[&](auto dfs2,int v,int p=-1)->void
    268         {
    269             // v is min
    270             ans+=2*d[v]*(dcs[d[v]]-s[v]);
    271             // v is lca
    272             ll subcnt=s[v]-1,lcnt=0;
    273             for(int w:adj[v])if(w!=p)
    274             {
    275                 lcnt+=(subcnt-s[w])*s[w];
    276                 dfs2(dfs2,w,v);
    277             }
    278             ans2+=(2*d[v]+1)*(lcnt/2);
    279         };
    280         dfs2(dfs2,0);
    281         for(int i=0;i<n;i++)
    282         {
    283             ans2+=i*dc[i]*(dc[i]-1);
    284         }
    285         cout<<ans-ans2<<"\n";
    286     }
    287 }
    288 ```
    289 
    290 ## [2063F1 - Counting Is Not Fun (Easy Version)](/contest/2063/problem/F1 "Codeforces Round 1000 (Div. 2)")
    291 
    292 Author: [chromate00](/profile/chromate00 "Expert chromate00")
    293 
    294 **Hint**
    295 
    296 The subproblem where you find the number of different balanced bracket sequences of length $2k$ is already well-known.
    297 
    298 Now recall everyone's favorite data structure to solve problems related to balanced bracket sequences — **the stack**!
    299 
    300 **Editorial**
    301 
    302 Tutorial is loading...
    303 
    304 **Code (C++)**
    305 
    306 ```
    307 #include<bits/stdc++.h>
    308 using namespace std;
    309 using ll=long long;
    310 const ll md=998244353;
    311  
    312 int main()
    313 {
    314     int t;cin>>t;
    315     vector<ll>ctl(5050);
    316     ctl[0]=1;
    317     for(int n=1;n<5050;n++)
    318     {
    319         for(int i=1;i<=n;i++)
    320         {
    321             ctl[n]=(ctl[n]+ctl[i-1]*ctl[n-i]%md)%md;
    322         }
    323     }
    324     while(t--)
    325     {
    326         int n;cin>>n;
    327         ll ans=ctl[n];
    328         cout<<ans<<" ";
    329         string s(2*n+2,'.');
    330         s[0]='(';s[2*n+1]=')';
    331         for(int a=0;a<n;a++)
    332         {
    333             int i,j;cin>>i>>j;
    334             ans=1;
    335             s[i]='(';
    336             s[j]=')';
    337             string stk;
    338             for(char c:s)
    339             {
    340                 if(c==')')
    341                 {
    342                     int cnt=0;
    343                     while(stk.back()!='(')
    344                     {
    345                         cnt++;
    346                         stk.pop_back();
    347                     }
    348                     stk.pop_back();
    349                     ans=(ans*ctl[cnt/2])%md;
    350                 }
    351                 else stk+=c;
    352             }
    353             cout<<ans<<" \n"[a+1==n];
    354         }
    355     }
    356 }
    357 ```
    358 
    359 ## [2063F2 - Counting Is Not Fun (Hard Version)](/contest/2063/problem/F2 "Codeforces Round 1000 (Div. 2)")
    360 
    361 Author: [chromate00](/profile/chromate00 "Expert chromate00")
    362 
    363 **Hint**
    364 
    365 In the solution of the easy subtask, we manually enumerated the minimal balanced subsequences, each time in $\mathcal{O}(n)$.
    366 
    367 You can show that most minimal balanced subsequences do not change when a new clue is added. What data structure will you choose in order to utilize this fact as much as possible?
    368 
    369 **Editorial**
    370 
    371 Tutorial is loading...
    372 
    373 **Code (C++)**
    374 
    375 ```
    376 #include<bits/stdc++.h>
    377 using namespace std;
    378 using ll=long long;
    379 const ll nil=-1;
    380 const ll md=998244353;
    381  
    382 ll pw(ll a,ll b)
    383 {
    384     ll c=1;
    385     while(b>0)
    386     {
    387         if(b&1)c=c*a%md;
    388         a=a*a%md;
    389         b>>=1;
    390     }
    391     return c;
    392 }
    393  
    394 int main()
    395 {
    396     cin.tie(0)->sync_with_stdio(0);
    397     vector<ll>fac(1010101,1),ctl(505050);
    398     for(int i=1;i<1010101;i++)fac[i]=fac[i-1]*i%md;
    399     for(int i=0;i<505050;i++)
    400     {
    401         ctl[i]=fac[i*2]*pw(fac[i]*fac[i+1]%md,md-2)%md;
    402     }
    403     ll t;cin>>t;
    404     while(t--)
    405     {
    406         ll n;cin>>n;
    407         vector<ll>L(n*2,nil),R(n*2,nil),P(n*2,nil),S(n*2);
    408         auto update=[&](ll x)
    409         {
    410             S[x]=1;
    411             if(L[x]!=nil)S[x]+=S[L[x]];
    412             if(R[x]!=nil)S[x]+=S[R[x]];
    413         };
    414         auto rotate=[&](ll x)
    415         {
    416             ll dummy;
    417             ll p=P[x];
    418             ll b=nil;
    419             if(p==nil)return;
    420             if(x==L[p])
    421             {
    422                 L[p]=b=R[x];
    423                 R[x]=p;
    424             }
    425             else
    426             {
    427                 R[p]=b=L[x];
    428                 L[x]=p;
    429             }
    430             P[x]=P[p];P[p]=x;
    431             if(b!=nil)P[b]=p;
    432             (P[x]!=nil?p==L[P[x]]?L[P[x]]:R[P[x]]:dummy)=x;
    433             update(p);update(x);
    434         };
    435         auto splay=[&](ll x)
    436         {
    437             while(P[x]!=nil)
    438             {
    439                 ll p=P[x];
    440                 ll g=P[p];
    441                 if(g!=nil)
    442                 {
    443                     if((x==L[p])==(p==L[g]))rotate(p);
    444                     else rotate(x);
    445                 }
    446                 rotate(x);
    447             }
    448         };
    449         update(0);
    450         for(int i=1;i<n*2;i++)
    451         {
    452             L[i]=i-1;
    453             P[i-1]=i;
    454             update(i);
    455         }
    456         splay(0);
    457         ll ans=ctl[n];
    458         cout<<ans<<" ";
    459         for(int i=0;i<n;i++)
    460         {
    461             ll li,ri;cin>>li>>ri;
    462             //li=(li+ans%(2*n))%(2*n);
    463             //ri=(ri+ans%(2*n))%(2*n);
    464             li--;ri--;
    465             splay(li);
    466             ans=ans*pw(ctl[S[li]/2],md-2)%md;
    467             ll lli=L[li];
    468             if(L[li]!=nil)P[L[li]]=nil;
    469             if(R[li]!=nil)P[R[li]]=nil;
    470             L[li]=nil;
    471             R[li]=nil;
    472             update(li);
    473             // now L[li] separated from tree
    474             // should not be affected in splay ri
    475             splay(ri);
    476             ll lri=L[ri];
    477             ll rri=R[ri];
    478             if(L[ri]!=nil)P[L[ri]]=nil;
    479             if(R[ri]!=nil)P[R[ri]]=nil;
    480             L[ri]=nil;
    481             R[ri]=nil;
    482             update(ri);
    483             if(lri!=nil)
    484             {
    485                 splay(lri);
    486                 ans=ans*ctl[S[lri]/2]%md;
    487             }
    488             if(lli!=nil&&rri!=nil)
    489             {
    490                 while(L[rri]!=nil)rri=L[rri];
    491                 splay(lli);
    492                 splay(rri);
    493                 P[lli]=rri;
    494                 L[rri]=lli;
    495                 update(rri);
    496                 ans=ans*ctl[S[rri]/2]%md;
    497             }
    498             else if(lli!=nil||rri!=nil)
    499             {
    500                 if(lli!=nil)
    501                 {
    502                     splay(lli);
    503                     ans=ans*ctl[S[lli]/2]%md;
    504                 }
    505                 else
    506                 {
    507                     splay(rri);
    508                     ans=ans*ctl[S[rri]/2]%md;
    509                 }
    510             }
    511             L[ri]=li;
    512             P[li]=ri;
    513             update(ri);
    514             // make dummy tree (for invariant maintaining)
    515             cout<<ans<<" \n"[i+1==n];
    516         }
    517     }
    518 }
    519 ```
    520 
    521 **UPD**: People pointed out that the intended solution in the tutorial is overkill. Yes, I acknowledge this. Please look into the newly added alternative solution if you want a more elegant idea.
    522 
    523 **Editorial (Alternative)**
    524 
    525 Consider maintaining the MBSes directly, but instead of using a complex data structure, we will use a small-to-large trick with linked lists. Precisely, every time we have to split a linked list, we will identify the smaller section and split it out in $\mathcal{O}(|small|)$ time, and then the amortized time complexity will be $\mathcal{O}(n \log n)$. In this solution, we do not consider bracket pairs as MBSes, for a specific reason.
    526 
    527 Given a linked list of indices and two nodes on it, we can identify the smaller section in $\mathcal{O}(|small|)$ by iterating over both lists at the same time, interlacing the operations. The list which hit the end earlier will be the smaller one, and then we immediately know the value of $|small|$.
    528 
    529 The issue is that you cannot identify the size of both lists in $\mathcal{O}(|small|)$ time. This is hard to fix using only a linked list. Instead, we will also maintain the implicit rooted tree structure of the bracket sequence. The MBSes correspond to vertices, and the bracket pairs correspond to edges. Initially, the tree just consists of one vertex of $2n$ brackets.
    530 
    531 Now, for each list node, we add a pointer to the corresponding tree vertex. Now we can know which tree vertex the list node corresponds to immediately, and if we bookkeep size informations in the tree vertices, we can also find the sum of two list sizes in $\mathcal{O}(1)$. Therefore we can now know the size of both lists in $\mathcal{O}(|small|)$ time.
    532 
    533 The only issue is with how to maintain the pointers to the tree vertices. But no problem, you can just do the small-to-large for this also. After splitting the tree vertex into two vertices and one edge, redirect the smaller list to the new smaller vertex. Theoretically there are enough ways to do this, such as swapping vertex indices. Also it is notable that it is not necessary to maintain the whole tree in this process, it is quite sufficient to just maintain it implicitly by just maintaining a sequence of sizes.
    534 
    535 The problem is solved online with $\mathcal{O}(n \log n)$ amortized time complexity.
    536 
    537 **Code (C++, by Mukundan314)**
    538 
    539 ```
    540 #pragma GCC optimize("O3,unroll-loops")
    541 
    542 #include <iostream>
    543 #include <numeric>
    544 #include <vector>
    545 
    546 constexpr int MAX_N = 3e5;
    547 constexpr long long MOD = 998244353;
    548 
    549 struct _inv_small {
    550   long long data[MAX_N + 2] = {0};
    551   constexpr _inv_small() {
    552     data[1] = 1;
    553     for (int i = 2; i <= MAX_N; i += 2) {
    554       data[i] = MOD - (MOD / i) * data[MOD % i] % MOD;
    555       data[i + 1] = MOD - (MOD / (i + 1)) * data[MOD % (i + 1)] % MOD;
    556     }
    557   }
    558 };
    559 
    560 constexpr _inv_small __inv_small;
    561 #define inv_small(x) __inv_small.data[x]
    562 
    563 #define inv(x) (x < MAX_N ? inv_small(x) : data[(x) - MAX_N])
    564 struct _inv {
    565   long long data[MAX_N + 3] = {0};
    566   constexpr _inv() {
    567     for (int i = 0; i <= MAX_N + 1; i += 2) {
    568       data[i] = MOD - (MOD / (i + MAX_N)) * inv(MOD % (i + MAX_N)) % MOD;
    569       data[i + 1] = MOD - (MOD / (i + MAX_N + 1)) * inv(MOD % (i + MAX_N + 1)) % MOD;
    570     }
    571   }
    572 };
    573 #undef inv
    574 
    575 constexpr _inv __inv;
    576 #define inv(x) (x < MAX_N ? inv_small(x) : __inv.data[(x) - MAX_N])
    577 
    578 struct _catalan {
    579   long long data[MAX_N + 2] = {1};
    580   constexpr _catalan() {
    581     for (int i = 1; i <= MAX_N; i += 2) {
    582       data[i] = (4 * i - 2) * data[i - 1] % MOD * inv(i + 1) % MOD;
    583       data[i + 1] = (4 * i + 2) * data[i] % MOD * inv(i + 2) % MOD;
    584     }
    585   }
    586 };
    587 
    588 constexpr _catalan __catalan;
    589 #define catalan(x) __catalan.data[x]
    590 
    591 struct _catalan_inv {
    592   long long data[MAX_N + 2] = {1};
    593   constexpr _catalan_inv() {
    594     for (int i = 1; i <= MAX_N; i += 2) {
    595       data[i] = inv(2) * inv(2 * i - 1) % MOD * data[i - 1] % MOD * (i + 1) % MOD;
    596       data[i + 1] = inv(2) * inv(2 * i + 1) % MOD * data[i] % MOD * (i + 2) % MOD;
    597     }
    598   }
    599 };
    600 
    601 constexpr _catalan_inv __catalan_inv;
    602 #define catalan_inv(x) __catalan_inv.data[x]
    603 
    604 int main() {
    605   std::cin.tie(0)->sync_with_stdio(0);
    606 
    607   int t;
    608   std::cin >> t;
    609 
    610   for (int _ = 0; _ < t; ++_) {
    611     int n;
    612     std::cin >> n;
    613 
    614     std::vector<bool> used(2 * n + 2);
    615 
    616     std::vector<int> point(2 * n + 2);
    617     std::iota(point.begin(), point.end(), 1);
    618 
    619     std::vector<int> size(2 * n + 2);
    620 
    621     std::vector<int> parent = {0};
    622     std::vector<int> parent_idx(2 * n + 2);
    623 
    624     used[0] = true;
    625     point[0] = 2 * n + 2, point[2 * n + 1] = 2 * n + 1;
    626     size[0] = 2 * n;
    627 
    628     long long ans = catalan(n);
    629 
    630     std::cout << ans << " ";
    631 
    632     for (int i = 0, l, r; i < n; ++i) {
    633       std::cin >> l >> r;
    634 
    635       point[l] = r + 1, point[r] = r;
    636       used[l] = true;
    637 
    638       int p = parent[parent_idx[l]];
    639 
    640       int out_ptr = p + 1, ins_ptr = l + 1;
    641       int out_size = 0, ins_size = 0;
    642 
    643       while (point[out_ptr] != out_ptr && point[ins_ptr] != ins_ptr) {
    644         out_size += !used[out_ptr];
    645         ins_size += !used[ins_ptr];
    646         out_ptr = point[out_ptr];
    647         ins_ptr = point[ins_ptr];
    648       }
    649 
    650       ans = (ans * catalan_inv(size[p] / 2)) % MOD;
    651 
    652       int upd_ptr;
    653       if (point[out_ptr] == out_ptr) {
    654         upd_ptr = p + 1;
    655         parent.push_back(p);
    656         parent[parent_idx[l]] = l;
    657 
    658         ins_size = size[p] - 2 - out_size;
    659         size[p] = out_size, size[l] = ins_size;
    660       } else {
    661         upd_ptr = l + 1;
    662         parent.push_back(l);
    663 
    664         out_size = size[p] - 2 - ins_size;
    665         size[p] = out_size, size[l] = ins_size;
    666       }
    667 
    668       ans = (ans * catalan(size[p] / 2)) % MOD * catalan(size[l] / 2) % MOD;
    669 
    670       while (point[upd_ptr] != upd_ptr) {
    671         parent_idx[upd_ptr] = parent.size() - 1;
    672         upd_ptr = point[upd_ptr];
    673       }
    674 
    675       std::cout << ans << " ";
    676     }
    677 
    678     std::cout << '\n';
    679   }
    680 }
    681 ```