#935587 (C++17(gcc12)) No.2563 色ごとのグループ

提出ソース
結果

問題	No.2563 色ごとのグループ
ユーザー	👑 p-adic
提出日時	2023-12-02 18:40:10
言語	C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
結果	TLE
実行時間	-
コード長	55,283 bytes
コンパイル時間	12,712 ms
コンパイル使用メモリ	297,892 KB
最終ジャッジ日時	2025-02-18 06:09:59
ジャッジサーバーID （参考情報）	judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 21 TLE * 1 -- * 13
権限があれば一括ダウンロードができます
ソースコード

raw source code
プレゼンテーションモードにする

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
// https://yukicoder.me/submissions/934698
// フリーズの原因を調べ中。
#ifdef INCLUDE_MAIN
inline void Solve()
{
  // // 数
  // // DEXPR( ll , bound_N , 100000 , 100 ); // 0が5個
  // // // DEXPR( ll , bound_N , 1000000000 , 100 ); // 0が9個
  // // // DEXPR( ll , bound_N , 1000000000000000000 , 100 ); // 0が18個
  // // CEXPR( TYPE_OF( bound_N ) , bound_M , bound_N );
  // // // DEXPR( ll , bound_M , 100000 , 100 ); // 0が5個
  // // // DEXPR( ll , bound_M , 1000000000 , 100 ); // 0が9個
  // // // DEXPR( ll , bound_M , 1000000000000000000 , 100 ); // 0が18個
  CIN( ll , N , M );
  // // CIN( ll , M );
  // // CIN( ll , N , M , K );
  // // CIN_ASSERT( N , 1 , bound_N ); // ランダムテスト用。上限のデフォルト値は10^5。
  // // CIN_ASSERT( M , 1 , bound_M ); // ランダムテスト用。上限のデフォルト値は10^5。
  // ll answer = 0;
  // // MP answer = 0;
  // // auto answer = Answer( N , M , K );
  // // COUT( answer );
  // RETURN( answer );
  // // 文字列
  // CIN( string , S );
  // // CIN( string , T );
  // ll answer = 0;
  // // MP answer = 0;
  // // auto answer = Answer( N , M , K );
  // // COUT( answer );
  // RETURN( answer );
  // 配列
  // CIN_A( ll , A , N );
  // CIN_A( ll , B , N );
  // ll A[bound_N]; // 関数（コンストラクタ）の引数に使う。長さのデフォルト値は10^5。
  // ll B[bound_N]; // 関数（コンストラクタ）の引数に使う。長さのデフォルト値は10^5。
  
  // MP answer = 0;
  // auto answer = Answer( N , M , K );
  // COUT( answer );
  // COUT_A( A , N );
  // RETURN( answer );
  // // 順列
  // vector<int> A( N );
  // vector<int> A_inv( N );
  // FOR( i , 0 , N ){
  //   cin >> A[i];
  //   A_inv[--A[i]] = i;
  // }
  // ll answer = 0;
  // // MP answer = 0;
  // // auto answer = Answer( N , M , K );
  // // COUT( answer );
  // // COUT_A( A , N );
  // RETURN( answer );
  UnionFindForest<int> uff( N );
  FOR( i , 0 , N ){
    CIN_ASSERT( Ci , 1 , N );
    uff.push_RightMost( --Ci );
  }
  // グラフ
  e<int>.resize( N );
  // e<path>.resize( N );
  FOR( j , 0 , M ){
    CIN_ASSERT( uj , 1 , N );
    CIN_ASSERT( vj , 1 , N );
    uj--;
    vj--;
    if( uff[uj] == uff[vj] ){
      uff.Graft( uj , vj );
    }
    // e<int>[uj].push_back( vj );
    // e<int>[vj].push_back( uj );
    // CIN( ll , wj );
    // e<path>[uj].push_back( { vj , wj } );
    // e<path>[vj].push_back( { uj , wj } );
  }
  ll answer = 0;
  cerr << __LINE__ << endl;
  vector<int> C(N); // int C[N]{};
  cerr << __LINE__ << endl;
  const uint& size = uff.GetSZOfRoot();
  cerr << __LINE__ << endl;
  FOR( i , 0 , size ){
    const int& Ci = uff[uff.GetRoot( i )];
    ASSERT( Ci , 0 , N - 1 );
    C[Ci]++;
  }
  cerr << __LINE__ << endl;
  FOR( i , 0 , N ){
    answer += max( C[i] - 1 , 0 );
  }
  cerr << __LINE__ << endl;
  // MP answer = 0;
  // auto answer = Answer( N , M , K );
  // COUT( answer );
  // COUT_A( A , N );
  RETURN( answer );
  // // 座標圧縮や単一クエリタイプなどのための入力格納
  // vector<T3<ll> > data( M );
  // FOR( j , 0 , M ){
  //   CIN( ll , x , y , z );
  //   data[j] = { x , y , z };
  // }
  // ll answer = 0;
  // // MP answer = 0;
  // // auto answer = Answer( N , M , K );
  // // COUT( answer );
  // // COUT_A( A , N );
  // RETURN( answer );
  
  // // 一般のクエリ
  // CIN( int , Q );
  // // DEXPR( int , bound_Q , 100000 , 100 ); // 基本不要。
  // // CIN_ASSERT( Q , 1 , bound_Q ); // 基本不要。
  // // vector<T3<int> > query( Q );
  // // vector<T2<int> > query( Q );
  // FOR( q , 0 , Q ){
  //   CIN( int , type );
  //   if( type == 1 ){
  //     CIN( int , x , y );
  //     // query[q] = { type , x , y };
  //   } else if( type == 2 ){
  //     CIN( int , x , y );
  //     // query[q] = { type , x , y };
  //   } else {
  //     CIN( int , x , y );
  //     // query[q] = { type , x , y };
  //   }
  //   // CIN( int , x , y );
  //   // // query[q] = { x , y };
  // }
  // // sort( query , query + Q );
  // // FOR( q , 0 , Q ){
  // //   auto& [x,y] = query[q];
  // //   // auto& [type,x,y] = query[q];
  // // }
  // auto answer = Answer( N , M , K );
  // // COUT( answer );
  // // COUT_A( A , N );
  // RETURN( answer );
  
  // // グリッド
  // // DEXPR( int , bound_H , 2000 , 30 );
  // // // DEXPR( int , bound_H , 100000 , 10 ); // 0が5個
  // // // CEXPR( int , bound_H , 1000000000 ); // 0が9個
  // // // CEXPR( int , bound_W , bound_H );
  // // static_assert( ll( bound_H ) * bound_W < ll( 1 ) << 31 );
  // // CEXPR( int , bound_HW , bound_H * bound_W );
  // // // CEXPR( int , bound_HW , 100000 ); // 0が5個
  // // // CEXPR( int , bound_HW , 1000000 ); // 0が6個
  // cin >> H >> W;
  // // SET_ASSERT( H , 1 , bound_H ); // ランダムテスト用。上限のデフォルト値は2*10^3。
  // // SET_ASSERT( W , 1 , bound_W ); // ランダムテスト用。上限のデフォルト値は2*10^3。
  // H_minus = H - 1;
  // W_minus = W - 1;
  // HW = H * W;
  // // assert( HW <= bound_HW ); // 基本不要。上限のデフォルト値は4*10^6。
  // vector<string> S( H );
  // FOR( i , 0 , H ){
  //   cin >> S[i];
  //   // SetEdgeOnGrid( S[i] , i , e<int> );
  //   // SetWallOnGrid( S[i] , i , non_wall );
  // }
  // // {h,w}へデコード: EnumHW( v )
  // // {h,w}をコード: EnumHW_inv( h , w );
  // // (i,j)->(k,h)の方向番号を取得: DirectionNumberOnGrid( i , j , k , h );
  // // v->wの方向番号を取得: DirectionNumberOnGrid( v , w );
  // // 方向番号の反転U<->D、R<->L: ReverseDirectionNumberOnGrid( n );
  // ll answer = 0;
  // // MP answer = 0;
  // // auto answer = Answer( N , M , K );
  // // COUT( answer );
  // // COUT_A( A , N );
  // RETURN( answer );
}
REPEAT_MAIN(1);
#else // INCLUDE_MAIN
#ifdef INCLUDE_SUB
template <typename PATH> list<PATH> E( const int& i )
{
  // list<PATH> answer{};
  list<PATH> answer = e<PATH>[i];
  // VVV 入力によらない処理は以下に挿入する。
  // AAA 入力によらない処理は以上に挿入する。
  return answer;
}
template <typename T> inline T F( const T& t ){ return f<T>[t]; }
template <typename T> inline T G( const int& i ){ return g<T>[i]; }
ll Naive( int N , int M , int K )
{
  ll answer = N + M + K;
  return answer;
}
ll Answer( ll N , ll M , ll K )
{
  // START_WATCH;
  ll answer = N + M + K;
  // // TLに準じる乱択や全探索。デフォルトの猶予は100.0[ms]。
  // CEXPR( double , TL , 2000.0 );
  // while( CHECK_WATCH( TL ) ){
  // }
  return answer;
}
inline void Experiment()
{
  // CEXPR( int , bound , 10 );
  // FOREQ( N , 0 , bound ){
  //   FOREQ( M , 0 , bound ){
  //     FOREQ( K , 0 , bound ){
  //    COUT( N , M , K , ":" , Naive( N , M , K ) );
  //     }
  //   }
  //   // cout << Naive( N ) << ",\n"[N==bound];
  // }
}
inline void SmallTest()
{
  // CEXPR( int , bound , 10 );
  // FOREQ( N , 0 , bound ){
  //   FOREQ( M , 0 , bound ){
  //     FOREQ( K , 0 , bound ){
  //    COMPARE( N , M , K );
  //     }
  //   }
  //   // COMPARE( N );
  // }
}
#define INCLUDE_MAIN
#include __FILE__
#else // INCLUDE_SUB
#ifdef INCLUDE_LIBRARY
/*
C-x 3 C-x o C-x C-fによるファイル操作用
BFS:
c:/Users/user/Documents/Programming/Mathematics/Geometry/Graph/BreadthFirstSearch/compress.txt
CoordinateCompress:
c:/Users/user/Documents/Programming/Mathematics/SetTheory/DirectProduct/CoordinateCompress/compress.txt
DFSOnTree
c:/Users/user/Documents/Programming/Mathematics/Geometry/Graph/DepthFirstSearch/Tree/a.hpp
Divisor:
c:/Users/user/Documents/Programming/Mathematics/Arithmetic/Prime/Divisor/compress.txt
Polynomial
c:/Users/user/Documents/Programming/Mathematics/Polynomial/compress.txt
UnionFind
c:/Users/user/Documents/Programming/Utility/VLTree/UnionFindForest/compress.txt
*/
// VVV 常設でないライブラリは以下に挿入する。
// １つ目のコンストラクタは領域を確保するだけなのでpush_RightMostで要素を追加する必要があることに注意。
TE <TY T>CL EntryOfVLTree{PU:T m_t;EntryOfVLTree<T>* m_left_branch;EntryOfVLTree<T>* m_right_branch;EntryOfVLTree<T>* m_leftmost_node;EntryOfVLTree<T
    >* m_rightmost_node;IN EntryOfVLTree();TE <TY Arg> IN EntryOfVLTree(CO Arg&);TE <TY Arg> IN EntryOfVLTree(CO Arg&,EntryOfVLTree<T>* CO&
    ,EntryOfVLTree<T>* CO&);IN EntryOfVLTree(CO EntryOfVLTree<T>&);EntryOfVLTree<T>& OP=(CO EntryOfVLTree<T>&);};
TE <TY T> IN EntryOfVLTree<T>::EntryOfVLTree(): m_t(),m_left_branch(TH),m_right_branch(TH),m_leftmost_node(TH),m_rightmost_node(TH){}TE <TY T> TE <TY 
    Arg> IN EntryOfVLTree<T>::EntryOfVLTree(CO Arg& t): EntryOfVLTree(t,TH,TH){}TE <TY T> TE <TY Arg> IN EntryOfVLTree<T>::EntryOfVLTree(CO Arg& t
    ,EntryOfVLTree<T>* CO& left_branch,EntryOfVLTree<T>* CO& right_branch): m_t(t),m_left_branch(left_branch),m_right_branch(right_branch
    ),m_leftmost_node(TH),m_rightmost_node(TH){}TE <TY T> IN EntryOfVLTree<T>::EntryOfVLTree(CO EntryOfVLTree<T>& e): m_t(e.m_t),m_left_branch(e
    .m_left_branch == &e?TH:e.m_left_branch),m_right_branch(e.m_right_branch == &e?TH:e.m_right_branch),m_leftmost_node(TH),m_rightmost_node(TH){if(e
    .m_leftmost_node != &e){m_leftmost_node = e.m_leftmost_node;m_rightmost_node = e.m_rightmost_node;}}TE <TY T> EntryOfVLTree<T>& EntryOfVLTree<T
    >::OP=(CO EntryOfVLTree<T>& e){m_t = e.m_t;m_left_branch =(e.m_left_branch == &e?TH:e.m_left_branch);m_right_branch =(e.m_right_branch == &e?TH:e
    .m_right_branch);if(e.m_leftmost_node == &e){m_leftmost_node = m_rightmost_node = TH;}else{m_leftmost_node = e.m_leftmost_node;m_rightmost_node = 
    e.m_rightmost_node;}RE *TH;}
TE <TY T>CL IteratorOfVLTree{PU:EntryOfVLTree<T>* m_p;IN IteratorOfVLTree()NE;IN IteratorOfVLTree(EntryOfVLTree<T>* CO&)NE;IN IteratorOfVLTree(CO 
    IteratorOfVLTree<T>&)NE;IN T& OP*()CO;IN T* OP->()CO;IN IteratorOfVLTree<T>& OP=(CO IteratorOfVLTree<T>&)NE;IteratorOfVLTree<T>& OP++(int)NE
    ;IteratorOfVLTree<T>& OP--(int)NE;IteratorOfVLTree<T>& OP[](CO int&);IteratorOfVLTree<T>& Shift()NE;TE <TY... Args> IteratorOfVLTree<T>& Shift(CO 
    int&,CO Args&...);IN bool IsLeaf()CO NE;IN bool IsLeftMost()CO NE;IN bool IsRightMost()CO NE;IN bool IsValid()CO NE;};
TE <TY T>CL COIteratorOfVLTree{PU:CO EntryOfVLTree<T>* m_p;IN COIteratorOfVLTree()NE;IN COIteratorOfVLTree(CO EntryOfVLTree<T>* CO&)NE;IN 
    COIteratorOfVLTree(CO COIteratorOfVLTree<T>&)NE;IN COIteratorOfVLTree(CO IteratorOfVLTree<T>&)NE;IN CO T& OP*()CO;IN CO T* OP->()CO;IN 
    COIteratorOfVLTree<T>& OP=(CO COIteratorOfVLTree<T>&)NE;IN COIteratorOfVLTree<T>& OP=(CO IteratorOfVLTree<T>&)NE;COIteratorOfVLTree<T>& OP++(int
    )NE;COIteratorOfVLTree<T>& OP--(int)NE;COIteratorOfVLTree<T>& OP[](CO int&);COIteratorOfVLTree<T>& Shift()NE;TE <TY... Args> COIteratorOfVLTree<T
    >& Shift(CO int&,CO Args&...);IN bool IsLeaf()CO NE;IN bool IsLeftMost()CO NE;IN bool IsRightMost()CO NE;IN bool IsValid()CO NE;ST IN bool Equal
    (CO IteratorOfVLTree<T>&,CO IteratorOfVLTree<T>&)NE;ST IN bool Equal(CO COIteratorOfVLTree<T>&,CO IteratorOfVLTree<T>&)NE;ST IN bool Equal(CO 
    IteratorOfVLTree<T>&,CO COIteratorOfVLTree<T>&)NE;ST IN bool Equal(CO COIteratorOfVLTree<T>&,CO COIteratorOfVLTree<T>&)NE;};
TE <TY T> IN IteratorOfVLTree<T>::IteratorOfVLTree()NE:m_p(nullptr){}TE <TY T> IN IteratorOfVLTree<T>::IteratorOfVLTree(EntryOfVLTree<T>* CO& p)NE
    :m_p(p){}TE <TY T> IN IteratorOfVLTree<T>::IteratorOfVLTree(CO IteratorOfVLTree<T>& itr)NE:m_p(itr.m_p){}TE <TY T> IN T& IteratorOfVLTree<T>::OP
    *()CO{RE m_p->m_t;}TE <TY T> IN T* IteratorOfVLTree<T>::OP->()CO{RE &(*(*TH));}TE <TY T> IN IteratorOfVLTree<T>& IteratorOfVLTree<T>::OP=(CO 
    IteratorOfVLTree<T>& itr)NE{m_p = itr.m_p;RE *TH;}TE <TY T>IteratorOfVLTree<T>& IteratorOfVLTree<T>::OP++(int)NE{if(m_p == nullptr){RE *TH;}if
    (m_p == m_p->m_right_branch){m_p = nullptr;}else{m_p = m_p->m_right_branch;}RE *TH;}TE <TY T>IteratorOfVLTree<T>& IteratorOfVLTree<T>::OP--(int
    )NE{if(m_p == nullptr){RE *TH;}if(m_p == m_p->m_left_branch){m_p = nullptr;}else{m_p = m_p->m_left_branch;}RE *TH;}TE <TY T>IteratorOfVLTree<T>& 
    IteratorOfVLTree<T>::OP[](CO int& n){if(n > 0){m_p = m_p->m_leftmost_node;for(int i = 1;i < n;i++){m_p = m_p->m_right_branch;}}else{if(n < 0){m_p 
    = m_p->m_rightmost_node;for(int i = -1;n < i;i--){m_p = m_p->m_left_branch;}}}RE *TH;}TE <TY T> IteratorOfVLTree<T>& IteratorOfVLTree<T>::Shift
    ()NE{RE *TH;}TE <TY T> TE <TY... Args> IteratorOfVLTree<T>& IteratorOfVLTree<T>::Shift(CO int& n,CO Args&... args){OP[](n);RE Shift(args...);}TE 
    <TY T> IN bool IteratorOfVLTree<T>::IsLeaf()CO NE{RE(m_p == nullptr)? false :(m_p == m_p->m_leftmost_node);}TE <TY T> IN bool IteratorOfVLTree<T
    >::IsLeftMost()CO NE{RE(m_p == nullptr)? false :(m_p == m_p->m_left_branch);}TE <TY T> IN bool IteratorOfVLTree<T>::IsRightMost()CO NE{RE(m_p == 
    nullptr)? false :(m_p == m_p->m_right_branch);}TE <TY T> IN bool IteratorOfVLTree<T>::IsValid()CO NE{RE m_p != nullptr;}TE <TY T> IN 
    COIteratorOfVLTree<T>::COIteratorOfVLTree()NE:m_p(nullptr){}TE <TY T> IN COIteratorOfVLTree<T>::COIteratorOfVLTree(CO EntryOfVLTree<T>* CO& p)NE
    :m_p(p){}TE <TY T> IN COIteratorOfVLTree<T>::COIteratorOfVLTree(CO COIteratorOfVLTree<T>& itr)NE:m_p(itr.m_p){}TE <TY T> IN COIteratorOfVLTree<T
    >::COIteratorOfVLTree(CO IteratorOfVLTree<T>& itr)NE:m_p(itr.m_p){}TE <TY T> IN CO T& COIteratorOfVLTree<T>::OP*()CO{RE m_p->m_t;};TE <TY T> IN 
    CO T* COIteratorOfVLTree<T>::OP->()CO{RE &(*(*TH));}TE <TY T> IN COIteratorOfVLTree<T>& COIteratorOfVLTree<T>::OP=(CO COIteratorOfVLTree<T>& itr
    )NE{m_p = itr.m_p;RE *TH;}TE <TY T> IN COIteratorOfVLTree<T>& COIteratorOfVLTree<T>::OP=(CO IteratorOfVLTree<T>& itr)NE{m_p = itr.m_p;RE *TH;}TE 
    <TY T>COIteratorOfVLTree<T>& COIteratorOfVLTree<T>::OP++(int)NE{if(m_p == nullptr){RE *TH;}if(m_p == m_p->m_right_branch){m_p = nullptr;}else{m_p 
    = m_p->m_right_branch;}RE *TH;}TE <TY T>COIteratorOfVLTree<T>& COIteratorOfVLTree<T>::OP--(int)NE{if(m_p == nullptr){RE *TH;}if(m_p == m_p
    ->m_left_branch){m_p = nullptr;}else{m_p = m_p->m_left_branch;}RE *TH;}TE <TY T>COIteratorOfVLTree<T>& COIteratorOfVLTree<T>::OP[](CO int& n){if
    (n > 0){m_p = m_p->m_leftmost_node;for(int i = 1;i < n;i++){m_p = m_p->m_right_branch;}}if(n < 0){m_p = m_p->m_rightmost_node;for(int i = -1;n < 
    i;i--){m_p = m_p->m_left_branch;}}RE *TH;}TE <TY T> COIteratorOfVLTree<T>& COIteratorOfVLTree<T>::Shift()NE{RE *TH;}TE <TY T> TE <TY... Args> 
    COIteratorOfVLTree<T>& COIteratorOfVLTree<T>::Shift(CO int& n,CO Args&... args){OP[](n);RE Shift(args...);}TE <TY T> IN bool COIteratorOfVLTree<T
    >::IsLeaf()CO NE{RE(m_p == nullptr)? false :(m_p == m_p->m_leftmost_mode);}TE <TY T> IN bool COIteratorOfVLTree<T>::IsLeftMost()CO NE{RE(m_p == 
    nullptr)? false :(m_p == m_p->m_left_branch);}TE <TY T> IN bool COIteratorOfVLTree<T>::IsRightMost()CO NE{RE(m_p == nullptr)? false :(m_p == m_p
    ->m_right_branch);}TE <TY T> IN bool COIteratorOfVLTree<T>::IsValid()CO NE{RE m_p != nullptr;}TE <TY T> IN bool COIteratorOfVLTree<T>::Equal(CO 
    IteratorOfVLTree<T>& itr0,CO IteratorOfVLTree<T>& itr1)NE{RE itr0.m_p == itr1.m_p;}TE <TY T> IN bool COIteratorOfVLTree<T>::Equal(CO 
    COIteratorOfVLTree<T>& itr0,CO IteratorOfVLTree<T>& itr1)NE{RE itr0.m_p == itr1.m_p;}TE <TY T> IN bool COIteratorOfVLTree<T>::Equal(CO 
    IteratorOfVLTree<T>& itr0,CO COIteratorOfVLTree<T>& itr1)NE{RE itr0.m_p == itr1.m_p;}TE <TY T> IN bool COIteratorOfVLTree<T>::Equal(CO 
    COIteratorOfVLTree<T>& itr0,CO COIteratorOfVLTree<T>& itr1)NE{RE itr0.m_p == itr1.m_p;}TE <TY T> IN bool OP==(CO IteratorOfVLTree<T>& itr0,CO 
    IteratorOfVLTree<T>& itr1)NE{RE COIteratorOfVLTree<T>::Equal(itr0,itr1);}TE <TY T> IN bool OP!=(CO IteratorOfVLTree<T>& itr0,CO IteratorOfVLTree
    <T>& itr1)NE{RE !(itr0 == itr1);}TE <TY T> IN bool OP==(CO COIteratorOfVLTree<T>& itr0,CO IteratorOfVLTree<T>& itr1)NE{RE COIteratorOfVLTree<T
    >::Equal(itr0,itr1);}TE <TY T> IN bool OP!=(CO COIteratorOfVLTree<T>& itr0,CO IteratorOfVLTree<T>& itr1)NE{RE !(itr0 == itr1);}TE <TY T> IN bool 
    OP==(CO IteratorOfVLTree<T>& itr0,CO COIteratorOfVLTree<T>& itr1)NE{RE COIteratorOfVLTree<T>::Equal(itr0,itr1);}TE <TY T> IN bool OP!=(CO 
    IteratorOfVLTree<T>& itr0,CO COIteratorOfVLTree<T>& itr1)NE{RE !(itr0 == itr1);}TE <TY T> IN bool OP==(CO COIteratorOfVLTree<T>& itr0,CO 
    COIteratorOfVLTree<T>& itr1)NE{RE COIteratorOfVLTree<T>::Equal(itr0,itr1);}TE <TY T> IN bool OP!=(CO COIteratorOfVLTree<T>& itr0,CO 
    COIteratorOfVLTree<T>& itr1)NE{RE !(itr0 == itr1);}
TE <TY Arg>CL WrappedType{PU:Arg m_t;TE <TY... ARGS> IN WrappedType(CO ARGS&... args);IN VO Set(CO Arg& t);IN CO Arg& Get()CO NE;};
TE <TY... Types>CL WrappedTypes{};
TE <TY Arg> TE <TY... ARGS> IN WrappedType<Arg>::WrappedType(CO ARGS&... args): m_t(args...){}TE <TY Arg> IN VO WrappedType<Arg>::Set(CO Arg& t){m_t 
    = t;}TE <TY Arg> IN CO Arg& WrappedType<Arg>::Get()CO NE{RE m_t;}
TE <TY T> CL VLTree;
TE <TY T>CL VLSubTree{PU:EntryOfVLTree<T> m_e;EntryOfVLTree<T>* m_p_root;uint m_SZ;IN VLSubTree();TE <TY Arg1,TY... Arg2> IN VLSubTree(CO Arg1&,CO 
    Arg2&...);TE <TY Arg> IN VLSubTree(CO WrappedType<Arg>& t);IN VLSubTree(CO VLSubTree<T>&);IN VLSubTree(EntryOfVLTree<T>&);IN VLSubTree(CO 
    IteratorOfVLTree<T>&);IN VLSubTree(CO int&,CO EntryOfVLTree<T>&);IN VLSubTree(CO int&,CO COIteratorOfVLTree<T>&);VO LeafToTree(CO VLSubTree<T>&
    );VO Graft(VLSubTree<T>&);virtual ~VLSubTree()= default;VLSubTree<T>& OP=(CO VLSubTree<T>&);IN CRUI SZ()CO NE;IN VO CutBranches();IN bool IsLeaf
    ()CO NE;IN VLSubTree<T> LeftMostSubTree();IN VLSubTree<T> RightMostSubTree();IN VLTree<T> LeftMostSubTreeCopy()CO;IN VLTree<T> 
    RightMostSubTreeCopy()CO;IN VO push_RightMost()CO NE;TE <TY Arg1,TY... Arg2> VO push_RightMost(CO Arg1&,CO Arg2&...);TE <TY... Args> VO 
    push_RightMost(CO VLTree<T>&,CO Args&...);TE <TY Arg> VO push_LeftMost(CO Arg&);VO pop_RightMost();VO pop_LeftMost();VO pop_Root();US iterator = 
    IteratorOfVLTree<T>;US CO_iterator = COIteratorOfVLTree<T>;IN iterator LeftMostNode()NE;IN CO_iterator LeftMostNode()CO NE;IN iterator 
    RightMostNode()NE;IN CO_iterator RightMostNode()CO NE;iterator LeftMostLeaf()NE;CO_iterator LeftMostLeaf()CO NE;iterator RightMostLeaf()NE
    ;CO_iterator RightMostLeaf()CO NE;IN iterator Root()NE;IN CO_iterator Root()CO NE;TE <TY... Args> IN iterator GetIterator(CO Args&...);TE <TY... 
    Args> IN CO_iterator GetIterator(CO Args&...)CO;TE <TY Arg> VO insert(CO iterator&,CO Arg&);iterator erase(iterator&);IN CO T& GetRoot()CO NE;IN 
    T& RefRoot()NE;IN VO SetRoot(CO T&);TE <TY... Args> IN CO T& GetNode(CO Args&...)CO;VLSubTree<T> OP[](CRUI);VLSubTree<T> OP[](iterator&);VLTree<T
    > OP[](CO CO_iterator&)CO;VLTree<T> GetBranchCopy(CRUI)CO;VLTree<T> GetBranchCopy(CO iterator&)CO;VLTree<T> GetBranchCopy(CO CO_iterator&)CO;VO 
    Concatenate(CO VLTree<T>&);VO Concatenate(CO iterator&,CO VLTree<T>&);bool CheckContain(CO iterator&)CO NE;bool CheckContain(CO CO_iterator&)CO 
    NE;string Display()CO;};
TE <TY T> IN VLSubTree<T>::VLSubTree(): m_e(),m_p_root(&m_e),m_SZ(0){}TE <TY T> TE <TY Arg1,TY... Arg2> IN VLSubTree<T>::VLSubTree(CO Arg1& t0,CO 
    Arg2&... t1): VLSubTree<T>(){push_RightMost(t0,t1...);}TE <TY T> TE <TY Arg> IN VLSubTree<T>::VLSubTree(CO WrappedType<Arg>& t): m_e(t.Get
    ()),m_p_root(&m_e),m_SZ(0){}TE <TY T> IN VLSubTree<T>::VLSubTree(CO VLSubTree<T>& a): m_e(a.m_e.m_t),m_p_root(&m_e),m_SZ(0){LeafToTree(a);}TE <TY 
    T>VLSubTree<T>::VLSubTree(EntryOfVLTree<T>& e):m_e(e),m_p_root(&e),m_SZ(0){EntryOfVLTree<T>* p = m_p_root->m_leftmost_node;if(p != m_p_root){m_SZ
    ++;EntryOfVLTree<T>* CO p_rightmost = m_p_root->m_rightmost_node;WH(p != p_rightmost){p = p->m_right_branch;m_SZ++;}}}TE <TY T> IN VLSubTree<T
    >::VLSubTree(CO IteratorOfVLTree<T>& itr): VLSubTree(*(itr.m_p)){}TE <TY T>VLSubTree<T>::VLSubTree(CO int& dummy,CO EntryOfVLTree<T>& e):m_e(e
    .m_t),m_p_root(&m_e),m_SZ(0){CO EntryOfVLTree<T>* p = e.m_leftmost_node;CO EntryOfVLTree<T>* CO p_rightmost = e.m_rightmost_node;bool b =(p != &e
    );WH(b){push_RightMost(VLTree<T>(dummy,*p));b =(p != p_rightmost);p = p->m_right_branch;}}TE <TY T> IN VLSubTree<T>::VLSubTree(CO int& dummy,CO 
    COIteratorOfVLTree<T>& itr): VLSubTree(dummy,*(itr.m_p)){}TE <TY T>VLSubTree<T>& VLSubTree<T>::OP=(CO VLSubTree<T>& a){if(TH != &a){CutBranches
    ();LeafToTree(a);}RE *TH;}TE <TY T>VO VLSubTree<T>::LeafToTree(CO VLSubTree<T>& a){m_p_root->m_t = a.m_p_root->m_t;EntryOfVLTree<T>* p = a
    .m_p_root->m_leftmost_node;CRUI N = a.m_SZ;for(uint n = 0;n < N;n++){push_RightMost(VLTree<T>(0,*p));p = p->m_right_branch;}RE;}TE <TY T> IN CRUI 
    VLSubTree<T>::SZ()CO NE{RE m_SZ;}TE <TY T> IN VO VLSubTree<T>::CutBranches(){WH(m_SZ > 0)pop_RightMost();}TE <TY T> IN bool VLSubTree<T>::IsLeaf
    ()CO NE{RE m_SZ == 0;}TE <TY T> IN VLSubTree<T> VLSubTree<T>::LeftMostSubTree(){RE VLSubTree(*(m_p_root->m_leftmost_node));}TE <TY T> IN 
    VLSubTree<T> VLSubTree<T>::RightMostSubTree(){RE VLSubTree(*(m_p_root->m_rightmost_node));}TE <TY T> IN VLTree<T> VLSubTree<T
    >::LeftMostSubTreeCopy()CO{RE VLTree<T>(0,*(m_p_root->m_leftmost_node));}TE <TY T> IN VLTree<T> VLSubTree<T>::RightMostSubTreeCopy()CO{RE VLTree
    <T>(0,*(m_p_root->m_rightmost_node));}TE <TY T> IN VO VLSubTree<T>::push_RightMost()CO NE{}TE <TY T> TE <TY Arg1,TY... Arg2>VO VLSubTree<T
    >::push_RightMost(CO Arg1& t0,CO Arg2&... t1){auto p = new EntryOfVLTree<T>(t0);EntryOfVLTree<T>*& p_rightmost = m_p_root->m_rightmost_node;if
    (p_rightmost == m_p_root){m_p_root->m_leftmost_node = p;}else{p->m_left_branch = p_rightmost;p_rightmost->m_right_branch = p;}p_rightmost = p
    ;m_SZ++;push_RightMost(t1...);RE;}TE <TY T> TE <TY... Args>VO VLSubTree<T>::push_RightMost(CO VLTree<T>& t0,CO Args&... t1){push_RightMost(t0
    .m_p_root->m_t);Concatenate(t0);push_RightMost(t1...);RE;}TE <TY T> TE <TY Arg>VO VLSubTree<T>::push_LeftMost(CO Arg& t){auto p = new 
    EntryOfVLTree<T>(t);EntryOfVLTree<T>*& p_leftmost = m_p_root->m_leftmost_node;if(p_leftmost == m_p_root){m_p_root->m_rightmost_node = p;}else{p
    ->m_right_branch = p_leftmost;p_leftmost->m_left_branch = p;}p_leftmost = p;m_SZ++;RE;}TE <TY T>VO VLSubTree<T>::pop_RightMost(){assert(m_SZ > 0
    );EntryOfVLTree<T>* p_rightmost = m_p_root->m_rightmost_node;VLSubTree<T> t{*p_rightmost};t.CutBranches();if(m_SZ == 1){m_p_root->m_leftmost_node 
    = m_p_root;m_p_root->m_rightmost_node = m_p_root;}else{EntryOfVLTree<T>* CO& p_rightmost_prev = p_rightmost->m_left_branch;m_p_root
    ->m_rightmost_node = p_rightmost_prev;p_rightmost_prev->m_right_branch = p_rightmost_prev;}delete p_rightmost;m_SZ--;RE;}TE <TY T>VO VLSubTree<T
    >::pop_LeftMost(){assert(m_SZ > 0);EntryOfVLTree<T>* p_leftmost = m_p_root->m_leftmost_node;VLSubTree<T> t{*p_leftmost};t.CutBranches();if(m_SZ 
    == 1){m_p_root->m_leftmost_node = m_p_root;m_p_root->m_rightmost_node = m_p_root;}else{EntryOfVLTree<T>* CO& p_leftmost_next = p_leftmost
    ->m_right_branch;m_p_root->m_leftmost_node = p_leftmost_next;p_leftmost_next->m_left_branch = p_leftmost_next;}delete p_leftmost;m_SZ--;RE;}TE 
    <TY T>VO VLSubTree<T>::pop_Root(){assert(m_SZ == 1);EntryOfVLTree<T>* p_unique_node = m_p_root->m_leftmost_node;m_p_root->m_t = p_unique_node
    ->m_t;m_p_root->m_leftmost_node = p_unique_node->m_leftmost_node;m_p_root->m_rightmost_node = p_unique_node->m_rightmost_node;delete 
    p_unique_node;EntryOfVLTree<T>* p_node = m_p_root->m_leftmost_node;m_SZ = 0;if(p_node != m_p_root){m_SZ++;WH(p_node != p_node->m_right_branch
    ){p_node = p_node->m_right_branch;m_SZ++;}}RE;}TE <TY T> IN TY VLSubTree<T>::iterator VLSubTree<T>::LeftMostNode()NE{RE IteratorOfVLTree<T
    >(m_p_root->m_leftmost_node);}TE <TY T> IN TY VLSubTree<T>::CO_iterator VLSubTree<T>::LeftMostNode()CO NE{RE COIteratorOfVLTree<T>(m_p_root
    ->m_leftmost_node);}TE <TY T> IN TY VLSubTree<T>::iterator VLSubTree<T>::RightMostNode()NE{RE IteratorOfVLTree<T>(m_p_root->m_rightmost_node);}TE 
    <TY T> IN TY VLSubTree<T>::CO_iterator VLSubTree<T>::RightMostNode()CO NE{RE COIteratorOfVLTree<T>(m_p_root->m_rightmost_node);}TE <TY T>TY 
    VLSubTree<T>::iterator VLSubTree<T>::LeftMostLeaf()NE{EntryOfVLTree<T>* p = m_p_root->m_leftmost_node;WH(p != p->m_leftmost_node){p = p
    ->m_leftmost_node;}RE IteratorOfVLTree<T>(p);}TE <TY T>TY VLSubTree<T>::CO_iterator VLSubTree<T>::LeftMostLeaf()CO NE{CO EntryOfVLTree<T>* p = 
    m_p_root->m_leftmost_node;WH(p != p->m_leftmost_node){p = p->m_leftmost_node;}RE COIteratorOfVLTree<T>(p);}TE <TY T>TY VLSubTree<T>::iterator 
    VLSubTree<T>::RightMostLeaf()NE{EntryOfVLTree<T>* p = m_p_root->m_rightmost_node;WH(p != p->m_rightmost_node){p = p->m_rightmost_node;}RE 
    IteratorOfVLTree<T>(p);}TE <TY T>TY VLSubTree<T>::CO_iterator VLSubTree<T>::RightMostLeaf()CO NE{CO EntryOfVLTree<T>* p = m_p_root
    ->m_rightmost_node;WH(p != p->m_rightmost_node){p = p->m_rightmost_node;}RE COIteratorOfVLTree<T>(p);}TE <TY T> IN TY VLSubTree<T>::iterator 
    VLSubTree<T>::Root()NE{RE IteratorOfVLTree<T>(m_p_root);}TE <TY T> IN TY VLSubTree<T>::CO_iterator VLSubTree<T>::Root()CO NE{RE 
    COIteratorOfVLTree<T>(m_p_root);}TE <TY T> TE <TY... Args> IN TY VLSubTree<T>::iterator VLSubTree<T>::GetIterator(CO Args&... args){RE Root
    ().Shift(args...);}TE <TY T> TE <TY... Args> IN TY VLSubTree<T>::CO_iterator VLSubTree<T>::GetIterator(CO Args&... args)CO{RE Root().Shift(args
    ...);}TE <TY T> TE <TY Arg>VO VLSubTree<T>::insert(CO TY VLSubTree<T>::iterator& itr,CO Arg& t){assert(CheckContain(itr));EntryOfVLTree<T>* CO& 
    p0 = itr.m_p;EntryOfVLTree<T>* CO& p1 = p0->m_right_branch;auto p = new EntryOfVLTree<T>(t,p0,p1);p1->m_left_branch = p;p0->m_right_branch = p
    ;m_SZ++;RE;}TE <TY T>TY VLSubTree<T>::iterator VLSubTree<T>::erase(TY VLSubTree<T>::iterator& itr){assert(CheckContain(itr));EntryOfVLTree<T>* CO 
    p = itr.m_p;EntryOfVLTree<T>* CO p0 = p->m_left_branch;EntryOfVLTree<T>* CO p1 = p->m_right_branch;if(! itr.IsLeaf()){VLSubTree<T> t_sub{*p}
    ;t_sub.CutBranches();}if(p0 != p){if(p != p1){itr++;p0->m_right_branch = p1;p1->m_left_branch = p0;}else{itr--;p0->m_right_branch = p0;m_p_root
    ->m_rightmost_node = p0;}}else{if(p != p1){itr++;p1->m_left_branch = p1;m_p_root->m_leftmost_node = p1;}else{itr = Root();m_p_root
    ->m_leftmost_node = m_p_root;m_p_root->m_rightmost_node = m_p_root;}}delete p;m_SZ--;RE itr;}TE <TY T> IN CO T& VLSubTree<T>::GetRoot()CO NE{RE 
    m_p_root->m_t;}TE <TY T> IN T& VLSubTree<T>::RefRoot()NE{RE m_p_root->m_t;}TE <TY T> IN VO VLSubTree<T>::SetRoot(CO T& t){m_p_root->m_t = t;}TE 
    <TY T> TE <TY... Args> IN CO T& VLSubTree<T>::GetNode(CO Args&... args)CO{RE *(GetIterator(args...));}TE <TY T>VLSubTree<T> VLSubTree<T>::OP[]
    (CRUI i){assert(i < m_SZ);if(i <= m_SZ / 2){EntryOfVLTree<T>* p = m_p_root->m_leftmost_node;for(uint n = 0;n < i;n++){p = p->m_right_branch;}RE 
    VLSubTree<T>(*p);}EntryOfVLTree<T>* p = m_p_root->m_rightmost_node;for(uint n = m_SZ - 1;n > i;n--){p = p->m_left_branch;}RE VLSubTree<T>(*p);}TE 
    <TY T>VLSubTree<T> VLSubTree<T>::OP[](TY VLSubTree<T>::iterator& itr){assert(CheckContain(itr));RE VLSubTree<T>(*(itr.m_p));}TE <TY T>VLTree<T> 
    VLSubTree<T>::OP[](CO TY VLSubTree<T>::CO_iterator& itr)CO{assert(CheckContain(itr));RE VLTree<T>(0,itr.m_p);}TE <TY T>VLTree<T> VLSubTree<T
    >::GetBranchCopy(CRUI i)CO{assert(i < m_SZ);if(i <= m_SZ / 2){CO EntryOfVLTree<T>* p = m_p_root->m_leftmost_node;for(uint n = 0;n < i;n++){p = p
    ->m_right_branch;}RE VLTree<T>(0,*p);}CO EntryOfVLTree<T>* p = m_p_root->m_rightmost_node;for(uint n = m_SZ - 1;n > i;n--){p = p->m_left_branch
    ;}RE VLTree<T>(0,*p);}TE <TY T>VLTree<T> VLSubTree<T>::GetBranchCopy(CO TY VLSubTree<T>::iterator& itr)CO{assert(CheckContain(itr));RE VLTree<T
    >(0,*(itr.m_p));}TE <TY T>VLTree<T> VLSubTree<T>::GetBranchCopy(CO TY VLSubTree<T>::CO_iterator& itr)CO{assert(CheckContain(itr));RE VLTree<T>(0
    ,*(itr.m_p));}TE <TY T>VO VLSubTree<T>::Concatenate(CO VLTree<T>& t){EntryOfVLTree<T>* CO p_rightmost = m_p_root->m_rightmost_node;assert
    (p_rightmost->m_rightmost_node == p_rightmost);if(m_p_root == p_rightmost){LeafToTree(t);}else{VLSubTree<T>(*p_rightmost).LeafToTree(t);}RE;}TE 
    <TY T>VO VLSubTree<T>::Concatenate(CO TY VLSubTree<T>::iterator& itr,CO VLTree<T>& t){assert(itr.IsLeaf());EntryOfVLTree<T>* CO p = itr.m_p;if
    (m_p_root == p){LeafToTree(t);}else{VLSubTree<T>(*p).LeafToTree(t);}RE;}TE <TY T>VO VLSubTree<T>::Graft(VLSubTree<T>& t){EntryOfVLTree<T>*& 
    p_rightmost = m_p_root->m_rightmost_node;if(m_p_root == p_rightmost){p_rightmost = m_p_root->m_leftmost_node = t.m_p_root;}else{t.m_p_root
    ->m_left_branch = p_rightmost;p_rightmost = p_rightmost->m_right_branch = t.m_p_root;}RE;}TE <TY T>bool VLSubTree<T>::CheckContain(CO iterator& 
    itr)CO NE{auto p0 = itr.m_p;auto p1 = m_p_root->m_leftmost_node;for(uint i = 0;i < m_SZ;i++){if(p0 == p1){RE true;}p1 = p1->m_right_branch;}RE 
    false;}TE <TY T>bool VLSubTree<T>::CheckContain(CO CO_iterator& itr)CO NE{auto p0 = itr.m_p;auto p1 = m_p_root->m_leftmost_node;for(uint i = 0;i 
    < m_SZ;i++){if(p0 == p1){RE true;}p1 = p1->m_right_branch;}RE false;}TE <TY T>string VLSubTree<T>::Display()CO{string s = to_string(m_p_root->m_t
    );s += "(";CO EntryOfVLTree<T>* p = m_p_root->m_leftmost_node;for(uint i = 0;i < m_SZ;i++){if(i > 0){s += ",";}s += VLTree<T>(0,*p).Display();p = 
    p->m_right_branch;}s += ")";RE s;}TE <TY T>bool OP==(CO VLTree<T>& t1,CO VLTree<T>& t2){if(t1.GetRoot()!= t2.GetRoot()){RE false;}if(t1.IsLeaf
    ()){RE t2.IsLeaf();}if(t2.IsLeaf()){RE false;}auto itr1 = t1.LeftMostNode();auto itr2 = t2.LeftMostNode();WH(itr1.IsValid()&& itr2.IsValid()){if
    (t1.GetBranchCopy(*itr1)!= t2.GetBranchCopy(*itr2)){RE false;}itr1++;itr2++;}RE !(itr1.IsValid()|| itr2.IsValid());}TE <TY T> IN bool OP!=(CO 
    VLTree<T>& t1,CO VLTree<T>& t2){RE !(t1 == t2);}<hide>
TE <TY T>CL EntryOfLinkedVE{PU:T m_t;uint m_prev_entry;uint m_next_entry;IN EntryOfLinkedVE();IN EntryOfLinkedVE(CRUI prev_entry,CRUI next_entry);IN 
    EntryOfLinkedVE(EntryOfLinkedVE<T>&& e);};
TE <TY T> IN EntryOfLinkedVE<T>::EntryOfLinkedVE(): m_t(),m_prev_entry(0),m_next_entry(0){}TE <TY T> IN EntryOfLinkedVE<T>::EntryOfLinkedVE(CRUI 
    prev_entry,CRUI next_entry): m_t(),m_prev_entry(prev_entry),m_next_entry(next_entry){}TE <TY T> IN EntryOfLinkedVE<T>::EntryOfLinkedVE
    (EntryOfLinkedVE<T>&& e): m_t(MO(e.m_t)),m_prev_entry(MO(e.m_prev_entry)),m_next_entry(MO(e.m_next_entry)){}
TE <TY T> CL LinkedVE;
TE <TY T>CL IteratorOfLinkedVE{PU:LinkedVE<T>* m_p;uint m_i;IN IteratorOfLinkedVE(LinkedVE<T>* CO& p,CRUI i)NE;IN IteratorOfLinkedVE(CO 
    IteratorOfLinkedVE<T>& itr)NE;IN T& OP*()CO;IN T* OP->()CO;IteratorOfLinkedVE<T>& OP=(CO IteratorOfLinkedVE<T>& itr)NE;IN VO OP++(int);IN VO OP
    --(int);IN CO LinkedVE<T>& GetLinkedVE()CO NE;IN LinkedVE<T>& RefLinkedVE()NE;IN CRUI GetIndex()CO NE;IN CRUI RefIndex()NE;};
TE <TY T>CL COIteratorOfLinkedVE{PU:CO LinkedVE<T>* m_p;uint m_i;IN COIteratorOfLinkedVE(CO LinkedVE<T>* CO& p,CRUI i)NE;IN COIteratorOfLinkedVE(CO 
    COIteratorOfLinkedVE<T>& itr)NE;IN COIteratorOfLinkedVE(CO IteratorOfLinkedVE<T>& itr)NE;IN CO T& OP*()CO;IN CO T* OP->()CO;COIteratorOfLinkedVE
    <T>& OP=(CO COIteratorOfLinkedVE<T>& itr)NE;COIteratorOfLinkedVE<T>& OP=(CO IteratorOfLinkedVE<T>& itr)NE;IN VO OP++(int);IN VO OP--(int);IN CO 
    LinkedVE<T>& GetLinkedVE()CO NE;IN CRUI GetIndex()CO NE;IN CRUI RefIndex()NE;ST IN bool Equal(CO IteratorOfLinkedVE<T>&,CO IteratorOfLinkedVE<T>&
    )NE;ST IN bool Equal(CO COIteratorOfLinkedVE<T>&,CO IteratorOfLinkedVE<T>&)NE;ST IN bool Equal(CO IteratorOfLinkedVE<T>&,CO COIteratorOfLinkedVE
    <T>&)NE;ST IN bool Equal(CO COIteratorOfLinkedVE<T>&,CO COIteratorOfLinkedVE<T>&)NE;};
TE <TY T> IN IteratorOfLinkedVE<T>::IteratorOfLinkedVE(LinkedVE<T>* CO& p,CRUI i)NE:m_p(p),m_i(i){}TE <TY T> IN IteratorOfLinkedVE<T
    >::IteratorOfLinkedVE(CO IteratorOfLinkedVE<T>& itr)NE:m_p(itr.m_p),m_i(itr.m_i){}TE <TY T> IN T& IteratorOfLinkedVE<T>::OP*()CO{RE(*m_p)[m_i]
    ;}TE <TY T> IN T* IteratorOfLinkedVE<T>::OP->()CO{RE &((*m_p)[m_i]);}TE <TY T> IN IteratorOfLinkedVE<T>& IteratorOfLinkedVE<T>::OP=(CO 
    IteratorOfLinkedVE<T>& itr)NE{m_p = itr.m_p;m_i = itr.m_i;RE *TH;}TE <TY T> IN VO IteratorOfLinkedVE<T>::OP++(int){m_i = m_p->m_entry[m_i]
    .m_next_entry;}TE <TY T> IN VO IteratorOfLinkedVE<T>::OP--(int){m_i = m_p->m_entry[m_i].m_prev_entry;}TE <TY T> IN CO LinkedVE<T>& 
    IteratorOfLinkedVE<T>::GetLinkedVE()CO NE{RE *m_p;}TE <TY T> IN LinkedVE<T>& IteratorOfLinkedVE<T>::RefLinkedVE()NE{RE *m_p;}TE <TY T> IN CRUI 
    IteratorOfLinkedVE<T>::GetIndex()CO NE{RE m_i;}TE <TY T> IN CRUI IteratorOfLinkedVE<T>::RefIndex()NE{RE m_i;}TE <TY T> IN COIteratorOfLinkedVE<T
    >::COIteratorOfLinkedVE(CO LinkedVE<T>* CO& p,CRUI i)NE:m_p(p),m_i(i){}TE <TY T> IN COIteratorOfLinkedVE<T>::COIteratorOfLinkedVE(CO 
    COIteratorOfLinkedVE<T>& itr)NE:m_p(itr.m_p),m_i(itr.m_i){}TE <TY T> IN COIteratorOfLinkedVE<T>::COIteratorOfLinkedVE(CO IteratorOfLinkedVE<T>& 
    itr)NE:m_p(itr.m_p),m_i(itr.m_i){}TE <TY T> IN CO T& COIteratorOfLinkedVE<T>::OP*()CO{RE(*m_p)[m_i];}TE <TY T> IN CO T* COIteratorOfLinkedVE<T
    >::OP->()CO{RE &((*m_p)[m_i]);}TE <TY T>COIteratorOfLinkedVE<T>& COIteratorOfLinkedVE<T>::OP=(CO COIteratorOfLinkedVE<T>& itr)NE{m_p = itr.m_p
    ;m_i = itr.m_i;RE *TH;}TE <TY T>COIteratorOfLinkedVE<T>& COIteratorOfLinkedVE<T>::OP=(CO IteratorOfLinkedVE<T>& itr)NE{m_p = itr.m_p;m_i = itr
    .m_i;RE *TH;}TE <TY T> IN VO COIteratorOfLinkedVE<T>::OP++(int){m_i = m_p->m_entry[m_i].m_next_entry;}TE <TY T> IN VO COIteratorOfLinkedVE<T>::OP
    --(int){m_i = m_p->m_entry[m_i].m_prev_entry;}TE <TY T> IN CO LinkedVE<T>& COIteratorOfLinkedVE<T>::GetLinkedVE()CO NE{RE *m_p;}TE <TY T> IN CRUI 
    COIteratorOfLinkedVE<T>::GetIndex()CO NE{RE m_i;}TE <TY T> IN CRUI COIteratorOfLinkedVE<T>::RefIndex()NE{RE m_i;}TE <TY T> IN bool 
    COIteratorOfLinkedVE<T>::Equal(CO IteratorOfLinkedVE<T>& itr0,CO IteratorOfLinkedVE<T>& itr1)NE{RE itr0.m_p == itr1.m_p && itr0.m_i == itr1.m_i
    ;}TE <TY T> IN bool COIteratorOfLinkedVE<T>::Equal(CO COIteratorOfLinkedVE<T>& itr0,CO IteratorOfLinkedVE<T>& itr1)NE{RE itr0.m_p == itr1.m_p && 
    itr0.m_i == itr1.m_i;}TE <TY T> IN bool COIteratorOfLinkedVE<T>::Equal(CO IteratorOfLinkedVE<T>& itr0,CO COIteratorOfLinkedVE<T>& itr1)NE{RE itr0
    .m_p == itr1.m_p && itr0.m_i == itr1.m_i;}TE <TY T> IN bool COIteratorOfLinkedVE<T>::Equal(CO COIteratorOfLinkedVE<T>& itr0,CO 
    COIteratorOfLinkedVE<T>& itr1)NE{RE itr0.m_p == itr1.m_p && itr0.m_i == itr1.m_i;}TE <TY T> IN bool OP==(CO IteratorOfLinkedVE<T>& itr0,CO 
    IteratorOfLinkedVE<T>& itr1)NE{RE COIteratorOfLinkedVE<T>::Equal(itr0,itr1);}TE <TY T> IN bool OP!=(CO IteratorOfLinkedVE<T>& itr0,CO 
    IteratorOfLinkedVE<T>& itr1)NE{RE !(itr0 == itr1);}TE <TY T> IN bool OP==(CO COIteratorOfLinkedVE<T>& itr0,CO IteratorOfLinkedVE<T>& itr1)NE{RE 
    COIteratorOfLinkedVE<T>::Equal(itr0,itr1);}TE <TY T> IN bool OP!=(CO COIteratorOfLinkedVE<T>& itr0,CO IteratorOfLinkedVE<T>& itr1)NE{RE !(itr0 == 
    itr1);}TE <TY T> IN bool OP==(CO IteratorOfLinkedVE<T>& itr0,CO COIteratorOfLinkedVE<T>& itr1)NE{RE COIteratorOfLinkedVE<T>::Equal(itr0,itr1);}TE 
    <TY T> IN bool OP!=(CO IteratorOfLinkedVE<T>& itr0,CO COIteratorOfLinkedVE<T>& itr1)NE{RE !(itr0 == itr1);}TE <TY T> IN bool OP==(CO 
    COIteratorOfLinkedVE<T>& itr0,CO COIteratorOfLinkedVE<T>& itr1)NE{RE COIteratorOfLinkedVE<T>::Equal(itr0,itr1);}TE <TY T> IN bool OP!=(CO 
    COIteratorOfLinkedVE<T>& itr0,CO COIteratorOfLinkedVE<T>& itr1)NE{RE !(itr0 == itr1);}
TE <TY T>CL LinkedVE{PU:VE<EntryOfLinkedVE<T> > m_entry;uint m_front_linked_entry;uint m_back_linked_entry;uint m_SZ_of_VE;uint m_SZ_of_link;IN 
    LinkedVE();IN LinkedVE(CRUI max_SZ);IN CO T& OP[](CRUI i)CO;IN T& OP[](CRUI i);uint GetLinkedEntry(CRUI i)CO;IN CRUI GetFrontLinkedEntryIndex()CO 
    NE;IN CRUI GetBackLinkedEntryIndex()CO NE;IN CRUI GetSZOfVE()CO NE;IN CRUI GetSZOfLink()CO NE;IN bool EmptyVE()CO NE;IN bool EmptyLink()CO NE;IN 
    VO push_back();TE <TY U> VO push_back(CO U& u);TE <TY U,TY... ARGS> IN VO push_back(CO U& u,CO ARGS&... args);IN VO SetPreviousLink(CRUI i,CRUI j
    );IN VO SetNexttLink(CRUI i,CRUI j);IN CRUI GetPreviousLinkIndex(CRUI i)CO;IN CRUI GetNexttLinkIndex(CRUI i)CO;CRUI DeLink(CRUI i);VO ReLink(CRUI 
    i);US iterator = IteratorOfLinkedVE<T>;US CO_iterator = COIteratorOfLinkedVE<T>;IN iterator GetIterator(CRUI i)NE;IN CO_iterator GetIterator(CRUI 
    i)CO NE;IN iterator BE()NE;IN CO_iterator BE()CO NE;IN iterator EN()NE;IN CO_iterator EN()CO NE;iterator erase(iterator& itr);IN EntryOfLinkedVE
    <T>& push_back_Body_0();IN VO push_back_Body_1(EntryOfLinkedVE<T>& e);};
TE <TY T> IN LinkedVE<T>::LinkedVE(): m_entry(1),m_front_linked_entry(0),m_back_linked_entry(0),m_SZ_of_VE(0),m_SZ_of_link(0){}TE <TY T> IN LinkedVE
    <T>::LinkedVE(CRUI max_SZ): m_entry(),m_front_linked_entry(0),m_back_linked_entry(0),m_SZ_of_VE(0),m_SZ_of_link(0){m_entry.reserve(max_SZ + 1
    );m_entry.push_back(EntryOfLinkedVE<T>());}TE <TY T> IN CO T& LinkedVE<T>::OP[](CRUI i)CO{RE m_entry[i].m_t;}TE <TY T> IN T& LinkedVE<T>::OP[]
    (CRUI i){RE m_entry[i].m_t;}TE <TY T>uint LinkedVE<T>::GetLinkedEntry(CRUI i)CO{uint linked_entry = m_front_linked_entry;for(uint j = 0;j < i;j
    ++){linked_entry = m_entry[linked_entry].m_next_entry;}RE linked_entry;}TE <TY T> IN CRUI LinkedVE<T>::GetFrontLinkedEntryIndex()CO NE{RE 
    m_front_linked_entry;}TE <TY T> IN CRUI LinkedVE<T>::GetBackLinkedEntryIndex()CO NE{RE m_back_linked_entry;}TE <TY T> IN CRUI LinkedVE<T
    >::GetSZOfVE()CO NE{RE m_SZ_of_VE;}TE <TY T> IN CRUI LinkedVE<T>::GetSZOfLink()CO NE{RE m_SZ_of_link;}TE <TY T> IN bool LinkedVE<T>::EmptyVE()CO 
    NE{RE m_SZ_of_VE == 0;}TE <TY T> IN bool LinkedVE<T>::EmptyLink()CO NE{RE m_SZ_of_link == 0;}TE <TY T> IN VO LinkedVE<T>::push_back(){}TE <TY T> 
    TE <TY U>VO LinkedVE<T>::push_back(CO U& u){EntryOfLinkedVE<T>& e = push_back_Body_0();e.m_t = u;push_back_Body_1(e);RE;}TE <TY T> TE <TY U,TY... 
    ARGS> IN VO LinkedVE<T>::push_back(CO U& u,CO ARGS&... args){push_back(u);push_back(args...);}TE <TY T> IN EntryOfLinkedVE<T>& LinkedVE<T
    >::push_back_Body_0(){m_entry.push_back(EntryOfLinkedVE<T>(m_SZ_of_VE,m_front_linked_entry));RE m_entry[m_SZ_of_VE];}TE <TY T> IN VO LinkedVE<T
    >::push_back_Body_1(EntryOfLinkedVE<T>& e){e.m_next_entry = m_SZ_of_VE + 1;m_entry[m_front_linked_entry].m_prev_entry = m_SZ_of_VE + 1
    ;m_back_linked_entry = m_SZ_of_VE;m_SZ_of_VE++;m_SZ_of_link++;}TE <TY T> IN VO LinkedVE<T>::SetPreviousLink(CRUI i,CRUI j){m_entry[i]
    .m_prev_entry = j;}TE <TY T> IN VO LinkedVE<T>::SetNexttLink(CRUI i,CRUI j){m_entry[i].m_next_entry = j;}TE <TY T> IN CRUI LinkedVE<T
    >::GetPreviousLinkIndex(CRUI i)CO{RE m_entry[i].m_prev_entry;}TE <TY T> IN CRUI LinkedVE<T>::GetNexttLinkIndex(CRUI i)CO{RE m_entry[i]
    .m_next_entry;}TE <TY T>CRUI LinkedVE<T>::DeLink(CRUI i){CO EntryOfLinkedVE<T>& e = m_entry[i];m_entry[e.m_prev_entry].m_next_entry = e
    .m_next_entry;m_entry[e.m_next_entry].m_prev_entry = e.m_prev_entry;if(m_front_linked_entry == i){m_front_linked_entry = e.m_next_entry;}if
    (m_back_linked_entry == i){m_back_linked_entry = e.m_prev_entry;}m_SZ_of_link--;RE e.m_next_entry;}TE <TY T>VO LinkedVE<T>::ReLink(CRUI i
    ){EntryOfLinkedVE<T>& current_entry = m_entry[i];if(m_SZ_of_link == 0){EntryOfLinkedVE<T>& EN_entry = m_entry[m_SZ_of_VE];EN_entry.m_prev_entry = 
    EN_entry.m_next_entry = i;current_entry.m_prev_entry = current_entry.m_next_entry = m_SZ_of_VE;m_front_linked_entry = m_back_linked_entry = i
    ;}else{uint prev;if(m_front_linked_entry > i){m_front_linked_entry = i;prev = m_SZ_of_VE;}else{prev = m_front_linked_entry;}if
    (m_back_linked_entry < i){m_back_linked_entry = i;}prev = m_entry[prev].m_next_entry;WH(prev < i){prev = m_entry[prev].m_next_entry;}CO uint next 
    = prev;EntryOfLinkedVE<T>& next_entry = m_entry[next];prev = next_entry.m_prev_entry;EntryOfLinkedVE<T>& prev_entry = m_entry[prev];prev_entry
    .m_next_entry = i;current_entry.m_prev_entry = prev;current_entry.m_next_entry = next;next_entry.m_prev_entry = i;}m_SZ_of_link++;RE;}TE <TY T> 
    IN TY LinkedVE<T>::iterator LinkedVE<T>::GetIterator(CRUI i)NE{RE TY LinkedVE<T>::iterator(TH,i);}TE <TY T> IN TY LinkedVE<T>::CO_iterator 
    LinkedVE<T>::GetIterator(CRUI i)CO NE{RE TY LinkedVE<T>::CO_iterator(TH,i);}TE <TY T> IN TY LinkedVE<T>::iterator LinkedVE<T>::BE()NE{RE TY 
    LinkedVE<T>::iterator(TH,m_front_linked_entry);}TE <TY T> IN TY LinkedVE<T>::CO_iterator LinkedVE<T>::BE()CO NE{RE TY LinkedVE<T>::CO_iterator(TH
    ,m_front_linked_entry);}TE <TY T> IN TY LinkedVE<T>::iterator LinkedVE<T>::EN()NE{RE TY LinkedVE<T>::iterator(TH,m_SZ_of_VE);}TE <TY T> IN TY 
    LinkedVE<T>::CO_iterator LinkedVE<T>::EN()CO NE{RE TY LinkedVE<T>::CO_iterator(TH,m_SZ_of_VE);}TE <TY T> TY LinkedVE<T>::iterator LinkedVE<T
    >::erase(TY LinkedVE<T>::iterator& itr){RE TY LinkedVE<T>::iterator(TH,DeLink(itr.m_i));}
TE <TY T>CL EntryOfUnionFindForest{PU:VLSubTree<T> m_node;uint m_pred_node;uint m_root;uint m_depth;IN EntryOfUnionFindForest();IN 
    EntryOfUnionFindForest(CO T& t,CRUI num);IN EntryOfUnionFindForest(EntryOfUnionFindForest&& e);};TE <TY T> IN EntryOfUnionFindForest<T
    >::EntryOfUnionFindForest(): m_node(),m_pred_node(0),m_root(0),m_depth(0){}TE <TY T> IN EntryOfUnionFindForest<T>::EntryOfUnionFindForest(CO T& t
    ,CRUI num): m_node(),m_pred_node(num),m_root(num),m_depth(0){m_node.SetRoot(t);}TE <TY T> IN EntryOfUnionFindForest<T>::EntryOfUnionFindForest
    (EntryOfUnionFindForest<T>&& e): m_node(),m_pred_node(MO(e.m_pred_node)),m_root(MO(e.m_root)),m_depth(MO(e.m_depth)){m_node.SetRoot(MO(e.m_node
    .m_p_root->m_t));}
TE <TY T=char>CL UnionFindForest :public LinkedVE<EntryOfUnionFindForest<T> >{PU:IN UnionFindForest(CRUI max_SZ);IN UnionFindForest(CRUI max_SZ,CRUI 
    SZ);IN CO VLSubTree<T>& GetSubTree(CRUI num)CO;IN CRUI GetPredecessorNode(CRUI num)CO;CRUI GetRootOfNode(CRUI num);uint GetRoot(CRUI num)CO;IN CO 
    T& OP[](CRUI num)CO;IN T& OP[](CRUI num);IN CRUI GetSZOfNode()CO NE;IN CRUI GetSZOfRoot()CO NE;IN VO push_RightMost();VO push_RightMost(CO T& t
    );TE <TY... ARGS> IN VO push_RightMost(CO T& t,CO ARGS&... args);IN VO push_back()= delete;TE <TY U> VO push_back(CO U& u)= delete;TE <TY U,TY... 
    ARGS> IN VO push_back(CO U& u,CO ARGS&... args)= delete;IN VO SetPreviousLink(CRUI i,CRUI j)= delete;IN VO SetNexttLink(CRUI i,CRUI j)= delete;IN 
    CRUI GetPreviousLinkIndex(CRUI i)CO = delete;IN CRUI GetNexttLinkIndex(CRUI i)CO = delete;CRUI DeLink(CRUI i)= delete;VO ReLink(CRUI i)= delete
    ;VO Graft(CRUI num0,CRUI num1);};
TE <TY T> IN UnionFindForest<T>::UnionFindForest(CRUI max_SZ): LinkedVE<EntryOfUnionFindForest<T> >(max_SZ){}TE <TY T> IN UnionFindForest<T
    >::UnionFindForest(CRUI max_SZ,CRUI SZ): UnionFindForest(max_SZ){T t{};for(int i=0;i<SZ;i++){push_RightMost(t);}}TE <TY T> IN CO VLSubTree<T>& 
    UnionFindForest<T>::GetSubTree(CRUI num)CO{RE LinkedVE<EntryOfUnionFindForest<T> >::OP[](num).m_node;}TE <TY T> IN CRUI UnionFindForest<T
    >::GetPredecessorNode(CRUI num)CO{RE LinkedVE<EntryOfUnionFindForest<T> >::OP[](num).m_pred_node;}TE <TY T>CRUI UnionFindForest<T>::GetRootOfNode
    (CRUI num){uint& root = LinkedVE<EntryOfUnionFindForest<T> >::OP[](num).m_root;if(root != LinkedVE<EntryOfUnionFindForest<T> >::OP[](root).m_root
    ){root = GetRootOfNode(root);}RE root;}TE <TY T>uint UnionFindForest<T>::GetRoot(CRUI num)CO{auto itr = LinkedVE<EntryOfUnionFindForest<T> >::BE
    ();for(uint i = 0;i < num;i++){itr++;}RE itr.GetIndex();}TE <TY T> IN CO T& UnionFindForest<T>::OP[](CRUI num)CO{RE LinkedVE
    <EntryOfUnionFindForest<T> >::OP[](num).m_node.GetRoot();}TE <TY T> IN T& UnionFindForest<T>::OP[](CRUI num){RE LinkedVE<EntryOfUnionFindForest<T
    > >::OP[](num).m_node.RefRoot();}TE <TY T> IN CRUI UnionFindForest<T>::GetSZOfNode()CO NE{RE LinkedVE<EntryOfUnionFindForest<T> >::GetSZOfVE
    ();}TE <TY T> IN CRUI UnionFindForest<T>::GetSZOfRoot()CO NE{RE LinkedVE<EntryOfUnionFindForest<T> >::GetSZOfLink();}TE <TY T> IN VO 
    UnionFindForest<T>::push_RightMost(){}TE <TY T>VO UnionFindForest<T>::push_RightMost(CO T& t){EntryOfLinkedVE<EntryOfUnionFindForest<T> >& e = 
    LinkedVE<EntryOfUnionFindForest<T> >::push_back_Body_0();e.m_t.m_node.SetRoot(t);e.m_t.m_pred_node = e.m_t.m_root = LinkedVE
    <EntryOfUnionFindForest<T> >::m_SZ_of_VE;LinkedVE<EntryOfUnionFindForest<T> >::push_back_Body_1(e);RE;}TE <TY T> TE <TY... ARGS> IN VO 
    UnionFindForest<T>::push_RightMost(CO T& t,CO ARGS&... args){push_RightMost(t);push_RightMost(args...);}TE <TY T>VO UnionFindForest<T>::Graft
    (CRUI num0,CRUI num1){CRUI e0_root_index = GetRootOfNode(num0);CRUI e1_root_index = GetRootOfNode(num1);if(e0_root_index == e1_root_index){RE
    ;}EntryOfUnionFindForest<T>& e0_root = LinkedVE<EntryOfUnionFindForest<T> >::OP[](e0_root_index);EntryOfUnionFindForest<T>& e1_root = LinkedVE
    <EntryOfUnionFindForest<T> >::OP[](e1_root_index);CO uint i0 =(e0_root.m_depth < e1_root.m_depth?0:1);CO uint i1 = 1 - i0;EntryOfUnionFindForest
    <T>* CO p_e_root[2] ={&e0_root,&e1_root};EntryOfUnionFindForest<T>& root_0 = *(p_e_root[i0]);EntryOfUnionFindForest<T>& root_1 = *(p_e_root[i1]
    );if(root_0.m_depth == root_1.m_depth){root_1.m_depth++;}root_1.m_node.Graft(root_0.m_node);LinkedVE<EntryOfUnionFindForest<T> >::DeLink(root_0
    .m_root);root_0.m_root = root_0.m_pred_node = root_1.m_root;RE;}
// AAA 常設でないライブラリは以上に挿入する。
#define INCLUDE_SUB
#include __FILE__
#else // INCLUDE_LIBRARY
// #define REACTIVE
// #define USE_GETLINE
#ifdef DEBUG
  #define _GLIBCXX_DEBUG
#define REPEAT_MAIN( BOUND ) START_MAIN; signal( SIGABRT , &AlertAbort ); AutoCheck( exec_mode , use_getline ); if( exec_mode == sample_debug_mode || 
    exec_mode == submission_debug_mode || exec_mode == library_search_mode ){ return 0; } else if( exec_mode == experiment_mode ){ Experiment(); 
    return 0; } else if( exec_mode == small_test_mode ){ SmallTest(); return 0; }; DEXPR( int , bound_test_case_num , BOUND , min( BOUND , 100 ) ); 
    int test_case_num = 1; if( exec_mode == solve_mode ){ if constexpr( bound_test_case_num > 1 ){ SET_ASSERT( test_case_num , 1 , 
    bound_test_case_num ); } } else if( exec_mode == random_test_mode ){ CERR( "ランダムテストを行う回数を指定してください。" ); SET_LL( 
    test_case_num ); } FINISH_MAIN
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , DEBUG_VALUE )
  #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック： " , ( MIN ) , ( ( MIN ) <= A ? "<=" : ">" ) , A , ( A <= ( MAX ) ? "<=" : ">" ) , ( MAX ) 
      ); assert( ( MIN ) <= A && A <= ( MAX ) )
  #define SET_ASSERT( A , MIN , MAX ) if( exec_mode == solve_mode ){ SET_LL( A ); ASSERT( A , MIN , MAX ); } else if( exec_mode == random_test_mode 
      ){ CERR( #A , " = " , ( A = GetRand( MIN , MAX ) ) ); } else { assert( false ); }
  #define SOLVE_ONLY static_assert( __FUNCTION__[0] == 'S' )
  #define CERR( ... ) VariadicCout( cerr , __VA_ARGS__ ) << endl
  #define COUT( ... ) VariadicCout( cout << "出力： " , __VA_ARGS__ ) << endl
  #define CERR_A( A , N ) OUTPUT_ARRAY( cerr , A , N ) << endl
  #define COUT_A( A , N ) cout << "出力： "; OUTPUT_ARRAY( cout , A , N ) << endl
  #define CERR_ITR( A ) OUTPUT_ITR( cerr , A ) << endl
  #define COUT_ITR( A ) cout << "出力： "; OUTPUT_ITR( cout , A ) << endl
#else
  #pragma GCC optimize ( "O3" )
  #pragma GCC optimize ( "unroll-loops" )
  #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
  #define REPEAT_MAIN( BOUND ) START_MAIN; CEXPR( int , bound_test_case_num , BOUND ); int test_case_num = 1; if constexpr( bound_test_case_num > 1 
      ){ SET_ASSERT( test_case_num , 1 , bound_test_case_num ); } FINISH_MAIN
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE )
  #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
  #define SET_ASSERT( A , MIN , MAX ) SET_LL( A ); ASSERT( A , MIN , MAX )
  #define SOLVE_ONLY 
  #define CERR( ... ) 
  #define COUT( ... ) VariadicCout( cout , __VA_ARGS__ ) << ENDL
  #define CERR_A( A , N ) 
  #define COUT_A( A , N ) OUTPUT_ARRAY( cout , A , N ) << ENDL
  #define CERR_ITR( A ) 
  #define COUT_ITR( A ) OUTPUT_ITR( cout , A ) << ENDL
#endif
#ifdef REACTIVE
  #define ENDL endl
#else
  #define ENDL "\n"
#endif
#ifdef USE_GETLINE
  #define SET_LL( A ) { GETLINE( A ## _str ); A = stoll( A_str ); }
  #define GETLINE_SEPARATE( SEPARATOR , ... ) SOLVE_ONLY; string __VA_ARGS__; VariadicGetline( cin , SEPARATOR , __VA_ARGS__ )
  #define GETLINE( ... ) SOLVE_ONLY; GETLINE_SEPARATE( '\n' , __VA_ARGS__ )
#else
  #define SET_LL( A ) cin >> A
  #define CIN( LL , ... ) SOLVE_ONLY; LL __VA_ARGS__; VariadicCin( cin , __VA_ARGS__ )
  #define SET_A( A , N ) SOLVE_ONLY; FOR( VARIABLE_FOR_CIN_A , 0 , N ){ cin >> A[VARIABLE_FOR_CIN_A]; }
  #define CIN_A( LL , A , N ) vector<LL> A( N ); SET_A( A , N );
#endif
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using lld = __float128;
template <typename INT> using T2 = pair<INT,INT>;
template <typename INT> using T3 = tuple<INT,INT,INT>;
template <typename INT> using T4 = tuple<INT,INT,INT,INT>;
using path = pair<int,ll>;
#define ATT __attribute__( ( target( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) ) )
#define START_MAIN int main(){ ios_base::sync_with_stdio( false ); cin.tie( nullptr )
#define FINISH_MAIN REPEAT( test_case_num ){ if constexpr( bound_test_case_num > 1 ){ CERR( "testcase " , VARIABLE_FOR_REPEAT_test_case_num , ":" ); 
    } Solve(); CERR( "" ); } }
#define START_WATCH chrono::system_clock::time_point watch = chrono::system_clock::now()
#define CURRENT_TIME static_cast<double>( chrono::duration_cast<chrono::microseconds>( chrono::system_clock::now() - watch ).count() / 1000.0 )
#define CHECK_WATCH( TL_MS ) ( CURRENT_TIME < TL_MS - 100.0 )
#define TYPE_OF( VAR ) decay_t<decltype( VAR )>
#define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE
#define CIN_ASSERT( A , MIN , MAX ) TYPE_OF( MAX ) A; SET_ASSERT( A , MIN , MAX )
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
#define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ )
#define FOREQINV( VAR , INITIAL , FINAL ) for( TYPE_OF( INITIAL ) VAR = INITIAL ; VAR >= FINAL ; VAR -- )
#define AUTO_ITR( ARRAY ) auto itr_ ## ARRAY = ARRAY .begin() , end_ ## ARRAY = ARRAY .end()
#define FOR_ITR( ARRAY ) for( AUTO_ITR( ARRAY ) , itr = itr_ ## ARRAY ; itr_ ## ARRAY != end_ ## ARRAY ; itr_ ## ARRAY ++ , itr++ )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT_ ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES )
#define SET_PRECISION( DECIMAL_DIGITS ) cout << fixed << setprecision( DECIMAL_DIGITS )
#define OUTPUT_ARRAY( OS , A , N ) FOR( VARIABLE_FOR_OUTPUT_ARRAY , 0 , N ){ OS << A[VARIABLE_FOR_OUTPUT_ARRAY] << (VARIABLE_FOR_OUTPUT_ARRAY==N-1?""
    :" "); } OS
#define OUTPUT_ITR( OS , A ) { auto ITERATOR_FOR_OUTPUT_ITR = A.begin() , END_FOR_OUTPUT_ITR = A.end(); bool VARIABLE_FOR_OUTPUT_ITR = 
    ITERATOR_FOR_COUT_ITR != END_FOR_COUT_ITR; while( VARIABLE_FOR_OUTPUT_ITR ){ OS << *ITERATOR_FOR_COUT_ITR; ( VARIABLE_FOR_OUTPUT_ITR = 
    ++ITERATOR_FOR_COUT_ITR != END_FOR_COUT_ITR ) ? OS : OS << " "; } } OS
#define RETURN( ... ) SOLVE_ONLY; COUT( __VA_ARGS__ ); return
#define COMPARE( ... ) auto naive = Naive( __VA_ARGS__ ); auto answer = Answer( __VA_ARGS__ ); bool match = naive == answer; COUT( #__VA_ARGS__ , ":" 
    , naive , match ? "==" : "!=" , answer ); if( !match ){ return; }
// 入出力用
template <class Traits> inline basic_istream<char,Traits>& VariadicCin( basic_istream<char,Traits>& is ) { return is; }
template <class Traits , typename Arg , typename... ARGS> inline basic_istream<char,Traits>& VariadicCin( basic_istream<char,Traits>& is , Arg& arg , 
    ARGS&... args ) { return VariadicCin( is >> arg , args... ); }
template <class Traits> inline basic_istream<char,Traits>& VariadicGetline( basic_istream<char,Traits>& is , const char& separator ) { return is; }
template <class Traits , typename Arg , typename... ARGS> inline basic_istream<char,Traits>& VariadicGetline( basic_istream<char,Traits>& is , const 
    char& separator , Arg& arg , ARGS&... args ) { return VariadicGetline( getline( is , arg , separator ) , separator , args... ); }
template <class Traits , typename Arg> inline basic_ostream<char,Traits>& VariadicCout( basic_ostream<char,Traits>& os , const Arg& arg ) { return os 
    << arg; }
template <class Traits , typename Arg1 , typename Arg2 , typename... ARGS> inline basic_ostream<char,Traits>& VariadicCout( basic_ostream<char,Traits
    >& os , const Arg1& arg1 , const Arg2& arg2 , const ARGS&... args ) { return VariadicCout( os << arg1 << " " , arg2 , args... ); }
// グリッド問題用
int H , W , H_minus , W_minus , HW;
vector<vector<bool> > non_wall;
inline T2<int> EnumHW( const int& v ) { return { v / W , v % W }; }
inline int EnumHW_inv( const int& h , const int& w ) { return h * W + w; }
const string direction[4] = {"U","R","D","L"};
// (i,j)->(k,h)の方向番号を取得
inline int DirectionNumberOnGrid( const int& i , const int& j , const int& k , const int& h ){return i<k?2:i>k?0:j<h?1:j>h?3:(assert(false),-1);}
// v->wの方向番号を取得
inline int DirectionNumberOnGrid( const int& v , const int& w ){auto [i,j]=EnumHW(v);auto [k,h]=EnumHW(w);return DirectionNumberOnGrid(i,j,k,h);}
// 方向番号の反転U<->D、R<->L
inline int ReverseDirectionNumberOnGrid( const int& n ){assert(0<=n&&n<4);return(n+2)%4;}
inline void SetEdgeOnGrid( const string& Si , const int& i , list<int> ( &e )[] , const char& walkable = '.' ){FOR(j,0,W){if(Si[j]==walkable){int v = 
    EnumHW_inv(i,j);if(i>0){e[EnumHW_inv(i-1,j)].push_back(v);}if(i+1<H){e[EnumHW_inv(i+1,j)].push_back(v);}if(j>0){e[EnumHW_inv(i,j-1)].push_back(v
    );}if(j+1<W){e[EnumHW_inv(i,j+1)].push_back(v);}}}}
inline void SetEdgeOnGrid( const string& Si , const int& i , list<path> ( &e )[] , const char& walkable = '.' ){FOR(j,0,W){if(Si[j]==walkable){const 
    int v=EnumHW_inv(i,j);if(i>0){e[EnumHW_inv(i-1,j)].push_back({v,1});}if(i+1<H){e[EnumHW_inv(i+1,j)].push_back({v,1});}if(j>0){e[EnumHW_inv(i,j-1
    )].push_back({v,1});}if(j+1<W){e[EnumHW_inv(i,j+1)].push_back({v,1});}}}}
inline void SetWallOnGrid( const string& Si , const int& i , vector<vector<bool> >& non_wall , const char& walkable = '.'  , const char& unwalkable = 
    '#' ){non_wall.push_back(vector<bool>(W));auto& non_wall_i=non_wall[i];FOR(j,0,W){non_wall_i[j]=Si[j]==walkable?true:(assert(Si[j]==unwalkable
    ),false);}}
// グラフ用
template <typename PATH> vector<list<PATH> > e;
template <typename T> map<T,T> f;
template <typename T> vector<T> g;
// デバッグ用
#ifdef DEBUG
  inline void AlertAbort( int n ) { CERR( 
      "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); }
  void AutoCheck( int& exec_mode , const bool& use_getline );
  inline void Solve();
  inline void Experiment();
  inline void SmallTest();
  inline void RandomTest();
  ll GetRand( const ll& Rand_min , const ll& Rand_max );
  int exec_mode;
  CEXPR( int , solve_mode , 0 );
  CEXPR( int , sample_debug_mode , 1 );
  CEXPR( int , submission_debug_mode , 2 );
  CEXPR( int , library_search_mode , 3 );
  CEXPR( int , experiment_mode , 4 );
  CEXPR( int , small_test_mode , 5 );
  CEXPR( int , random_test_mode , 6 );
  #ifdef USE_GETLINE
    CEXPR( bool , use_getline , true );
  #else
    CEXPR( bool , use_getline , false );
  #endif
#endif
// 圧縮用
#define TE template
#define TY typename
#define US using
#define ST static
#define IN inline
#define CL class
#define PU public
#define OP operator
#define CE constexpr
#define CO const
#define NE noexcept
#define RE return 
#define WH while
#define VO void
#define VE vector
#define LI list
#define BE begin
#define EN end
#define SZ size
#define MO move
#define TH this
#define CRI CO int&
#define CRUI CO uint&
#define CRL CO ll&
// VVV 常設ライブラリは以下に挿入する。
// AAA 常設ライブラリは以上に挿入する。
#define INCLUDE_LIBRARY
#include __FILE__
#endif // INCLUDE_LIBRARY
#endif // INCLUDE_SUB
#endif // INCLUDE_MAIN
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX