QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#787308#9743. 重心树GodwangAC ✓44ms20288kbC++235.6kb2024-11-27 11:03:052024-11-27 11:03:10

Judging History

你现在查看的是最新测评结果

  • [2024-11-27 11:03:10]
  • 评测
  • 测评结果:AC
  • 用时:44ms
  • 内存:20288kb
  • [2024-11-27 11:03:05]
  • 提交

answer

#include <iostream>
using namespace std;
#include <set>
#include <algorithm>
#include <cmath>
#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <string.h>
#include <stdlib.h>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <stack>
#include <queue>
#include <ctype.h>
#include <vector>
#include <random>
#include<list> 
#define ll long long
#define ull unsigned long long
#define pb push_back
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define pii pair<int, int>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define pll pair<ll, ll>
#define lowbit(x) ((x)&(-x))
ll extend_gcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll d = extend_gcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
ll fastpow(ll a, ll n, ll mod)
{
    ll ans = 1;
    a %= mod;
    while (n)
    {
        if (n & 1)
            ans = (ans * a) % mod; //% mod
        a = (a * a) % mod;         //% mod
        n >>= 1;
    }
    return ans;
}

inline void write(__int128 x)
{
    if (x > 9)
    {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}
__int128 sqrt(__int128 m)
{
    __int128 leftt = 0, rightt = ((__int128)1) << 51, ret = -1, mid;
    while (leftt < rightt)
    {
        mid = (leftt + rightt) / 2;
        if (mid * mid > m)
        {
            rightt = mid;
        }    
        else
        {
            leftt = mid + 1;
            ret = mid;
        }
    }
    return ret;
}

const double eps = 1e-6;
int sgn(double x)
{
    if(fabs(x)<eps)
    {
        return 0;
    }
    else return x<0?-1:1;
}

struct Point
{
    double x,y;
    Point()
    {

    }
    Point(double x,double y):x(x),y(y)
    {

    }
    Point operator + (Point B)
    {
        return Point(x+B.x,y+B.y);
    }
    Point operator - (Point B)
    {
        return Point(x-B.x,y-B.y);
    }
    bool operator == (Point B)
    {
        return sgn(x-B.x)==0&&sgn(y-B.y)==0;
    }
    bool operator < (Point B)
    {
        return sgn(x-B.x)<0||(sgn(x-B.x)==0&&sgn(y-B.y)<0);
    }
};
typedef Point Vector;
double Cross(Vector A,Vector B)//叉积
{
    return A.x*B.y-A.y*B.x;
}
double Distance(Point A,Point B)
{
    return hypot(A.x-B.x,A.y-B.y);
}
int Convex_hull(Point *p,int n,Point *ch)
{
    n=unique(p,p+n)-p;
    sort(p,p+n);
    int v=0;

    for(int i=0;i<n;i++)
    {
        while (v>1&&sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-1]))<=0)
        {
            v--;
        }
        ch[v++]=p[i];
    }

    int j=v;

    for(int i=n-2;i>=0;i--)
    {
        while (v>j&&sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-1]))<=0)
        {
            v--;
        }
        ch[v++]=p[i];
    }
    if(n>1)
    {
        v--;
    }
    return v;
}

int kmp(string s, string p)
{
    int ans = 0, lastt = -1;
    int lenp = p.size();
    vector<int > Next(lenp+3,0);
    rep(i, 1, lenp - 1)
    {
        int j = Next[i];
        while (j && p[j] != p[i])
        {
            j = Next[j];
        }
        if (p[j] == p[i])
        {
            Next[i + 1] = j + 1;
        }
        else
        {
            Next[i + 1] = 0;
        }
    }
    int lens = s.size();
    int j = 0;
    rep(i, 0, lens - 1)
    {
        while (j && s[i] != p[j])
        {
            j = Next[j];
        }
        if (s[i] == p[j])
        {
            j++;
        }
        if (j == lenp)
        {
            ans++;
        }
    }
    return ans;
}

int dir[4][2] =
    {
        {-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 左右上下
// int dir[8][2]={
//         {-1, 0}, {0, 1}, {1, 0}, {0, -1},{-1,-1},{-1,1},{1,-1},{1,1}
// };

#define endl '\n'//交互题请删除本行
const ll inf = 1000000000000000000ll;
const ll mod1 = 998244353ll, P1 = 131, mod2 = 1e9 + 7ll, P2 = 13331;
ll inverse(ll x)
{
    return fastpow(x,mod1-2,mod1);
}

const int N = 1e6 + 10, M = 1e6 + 10;

///////////////////////////////////

int tt;

int n;

int s[N];

vector<int > v[N];

vector<pii > ans;

///////////////////////////////////

bool cmp(int x,int y)
{
    return x>y;
}

int find_set(int x)
{
    return x==s[x]?x:s[x]=find_set(s[x]);
}

void merge(int x,int y)
{
    int rooty=find_set(y);

    if(x==rooty)
    {
        return;
    }
    s[rooty]=x;
    ans.pb({x,rooty});
}

///////////////////////////////////

void init()
{
    ans.clear();
    rep(i,1,n)
    {
        s[i]=i;
    }
    rep(i,1,n)
    {
        v[i].clear();
    }
}

///////////////////////////////////

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//交互题请删除本行
  //  freopen("ain.txt", "r", stdin); freopen("aout.txt", "w", stdout);
    
    cin>>tt;
    while (tt--)
    {
        cin>>n;
        init();
        rep(i,1,n)
        {
            int num;
            cin>>num;
            rep(j,1,num)
            {
                int x;
                cin>>x;
                v[x].pb(i);
                //
               // cout<<i<<" "<<x<<endl;
            }
        }

        rep(i,1,n)
        {
            sort(v[i].begin(),v[i].end(),cmp);
        }

        per(i,1,n)
        {
            for(auto j:v[i])
            {
                //
               // cout<<j<<" "<<i<<endl;
                merge(j,i);
            }
        }

        for(auto i:ans)
        {
            cout<<i.first<<" "<<i.second<<endl;
        }


    }
    
    


    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5728kb

input:

2
4
2 3 4
1 3
0
0
3
1 3
1 3
0

output:

1 4
2 3
1 2
2 3
1 2

result:

ok Accepted (2 test cases)

Test #2:

score: 0
Accepted
time: 15ms
memory: 5676kb

input:

40000
3
2 2 3
0
0
2
1 2
0
4
2 4 3
1 4
0
0
5
1 3
2 5 4
1 5
0
0
4
3 2 3 4
0
0
0
2
1 2
0
2
1 2
0
5
1 2
3 3 4 5
0
0
0
2
1 2
0
2
1 2
0
5
4 2 3 4 5
0
0
0
0
4
1 2
2 3 4
0
0
5
2 5 4
1 5
1 4
0
0
2
1 2
0
5
1 2
3 3 4 5
0
0
0
5
2 2 3
0
2 4 5
0
0
5
2 5 4
1 5
1 4
0
0
5
2 2 4
2 3 5
0
0
0
4
1 3
1 4
1 4
0
4
2 4 3
1 ...

output:

1 3
1 2
1 2
2 4
1 2
1 3
3 5
2 3
2 4
1 2
1 4
1 3
1 2
1 2
1 2
2 5
2 4
2 3
1 2
1 2
1 2
1 5
1 4
1 3
1 2
2 4
2 3
1 2
2 5
1 2
3 4
1 3
1 2
2 5
2 4
2 3
1 2
3 5
3 4
1 3
1 2
2 5
1 2
3 4
1 3
2 5
1 4
2 3
1 2
3 4
2 3
1 2
2 4
1 2
1 3
2 3
1 2
3 5
1 3
2 4
1 2
1 2
2 3
1 2
3 5
3 4
2 3
1 2
1 2
3 4
2 3
1 2
4 5
2 4
1 2
...

result:

ok Accepted (40000 test cases)

Test #3:

score: 0
Accepted
time: 8ms
memory: 5680kb

input:

10000
5
2 3 4
1 5
1 5
0
0
4
2 3 4
1 3
0
0
7
1 2
3 4 7 6
1 4
0
1 7
0
0
2
1 2
0
2
1 2
0
8
1 3
1 4
3 4 5 6
2 7 8
0
0
0
0
4
2 2 4
0
1 4
0
4
1 2
2 3 4
0
0
4
1 2
2 3 4
0
0
2
1 2
0
7
3 3 4 6
1 7
1 7
0
1 6
0
0
4
2 4 3
1 4
0
0
3
2 2 3
0
0
6
2 5 4
1 6
1 4
0
1 6
0
3
2 2 3
0
0
5
3 2 5 4
0
1 5
0
0
7
2 4 6
1 5
1 ...

output:

3 5
2 3
1 4
1 2
1 4
2 3
1 2
5 7
2 5
2 6
3 4
2 3
1 2
1 2
1 2
4 8
4 7
3 6
3 5
3 4
2 3
1 2
3 4
1 3
1 2
2 4
2 3
1 2
2 4
2 3
1 2
1 2
3 7
2 3
5 6
1 5
1 4
1 2
2 4
1 2
1 3
1 3
1 2
5 6
2 5
1 2
3 4
1 3
1 3
1 2
3 5
1 3
1 4
1 2
5 7
4 5
1 6
3 4
2 3
1 2
1 2
5 8
3 7
2 3
5 6
2 5
1 2
1 4
2 7
5 6
4 5
2 4
1 2
1 3
5 7
...

result:

ok Accepted (10000 test cases)

Test #4:

score: 0
Accepted
time: 10ms
memory: 5804kb

input:

10000
10
2 6 7
2 8 4
1 8
0
1 9
1 10
1 9
1 10
0
0
10
3 2 8 5
4 3 9 7 10
0
1 8
0
1 9
0
0
0
0
9
2 2 5
3 3 7 6
0
1 7
2 8 9
0
0
0
0
3
2 2 3
0
0
6
3 4 3 6
1 4
0
0
1 6
0
10
3 2 4 7
2 10 8
1 10
0
1 8
1 9
1 9
0
0
0
3
1 3
1 3
0
5
2 5 4
1 5
1 4
0
0
2
1 2
0
9
3 2 3 7
0
4 5 6 8 9
1 5
0
0
0
0
0
6
4 2 3 4 6
0
0
0
...

output:

8 10
6 8
7 9
5 7
3 6
2 3
1 5
1 2
2 4
2 10
6 9
2 6
4 8
1 4
2 7
1 5
2 3
1 2
5 9
5 8
4 7
2 4
2 6
1 5
2 3
1 2
1 3
1 2
5 6
1 5
2 4
1 2
1 3
3 10
2 3
7 9
6 7
5 8
2 5
1 6
1 4
1 2
2 3
1 2
2 5
1 2
3 4
1 3
1 2
3 9
3 8
1 7
3 6
4 5
3 4
1 3
1 2
5 6
1 5
1 4
1 3
1 2
3 9
1 3
6 8
5 6
5 7
4 5
1 4
1 2
1 2
6 7
3 6
1 3
3...

result:

ok Accepted (10000 test cases)

Test #5:

score: 0
Accepted
time: 2ms
memory: 5716kb

input:

16
392
4 2 3 165 13
0
2 4 12
0
4 177 7 9 23
2 187 16
0
1 13
0
1 13
2 208 27
0
2 14 22
0
1 23
2 19 20
1 208
3 21 25 27
0
0
0
0
0
2 208 29
0
2 32 31
3 44 40 38
1 208
0
1 44
0
3 35 49 52
1 42
2 36 208
0
0
1 44
1 42
1 49
1 60
2 79 213
0
3 46 79 57
2 47 48
1 60
0
0
0
0
1 213
1 79
1 64
1 57
2 79 63
2 62 2...

output:

383 392
377 383
389 391
386 389
382 390
379 382
378 386
373 378
384 388
377 384
385 387
380 385
372 373
377 380
370 379
364 370
376 381
371 376
364 372
367 377
364 367
361 371
353 361
373 375
367 374
349 353
364 369
364 368
358 366
357 365
356 357
362 364
356 362
348 356
340 348
339 340
333 339
329 ...

result:

ok Accepted (16 test cases)

Test #6:

score: 0
Accepted
time: 2ms
memory: 5720kb

input:

4
502
3 3 253 10
3 7 8 13
2 15 18
1 15
2 6 253
0
1 24
0
1 18
0
2 23 20
2 258 21
1 33
2 24 17
1 24
1 20
0
2 25 26
3 27 42 264
0
2 22 31
0
1 33
2 30 34
0
0
0
1 42
2 265 37
0
0
1 45
0
0
2 269 52
2 269 44
0
1 45
1 56
2 51 58
3 43 47 269
2 54 50
0
0
1 60
1 51
0
1 58
2 53 269
0
0
2 61 63
0
1 60
2 278 67
1...

output:

498 502
498 501
497 500
488 497
493 499
492 498
489 492
489 496
493 495
485 494
490 493
488 490
481 489
472 481
489 491
485 488
469 472
479 485
471 479
470 471
477 487
476 486
472 476
464 470
479 484
477 483
475 482
466 475
463 469
470 480
460 464
470 478
469 477
462 466
460 462
464 474
463 473
459 ...

result:

ok Accepted (4 test cases)

Test #7:

score: 0
Accepted
time: 1ms
memory: 5696kb

input:

1
422
2 9 195
1 9
4 5 195 11 8
1 13
1 13
3 212 12 25
2 16 14
0
0
2 18 212
2 19 31
0
0
0
2 22 29
1 27
1 22
0
1 27
3 221 26 30
1 31
0
1 222
2 33 37
2 33 35
0
0
1 222
1 34
0
0
1 40
2 48 49
1 48
0
2 38 229
2 42 41
0
1 56
1 42
0
0
1 50
3 86 47 238
2 86 51
1 86
0
1 56
1 50
0
0
2 238 58
2 94 57
1 238
1 96
...

output:

419 422
417 419
411 421
412 420
410 412
413 417
410 413
414 418
414 416
414 415
411 414
409 411
405 409
405 410
398 408
403 407
393 403
401 406
391 401
404 405
395 404
392 395
390 392
388 390
380 388
371 380
387 393
380 387
392 402
382 391
377 382
398 400
392 399
397 398
395 397
395 396
362 371
352 ...

result:

ok Accepted (1 test case)

Test #8:

score: 0
Accepted
time: 19ms
memory: 5816kb

input:

100
509
3 21 3 252
1 21
0
2 23 18
3 252 8 25
2 252 14
2 11 26
0
1 18
1 252
0
1 252
1 26
0
1 34
2 42 22
1 28
1 28
2 24 252
1 51
2 72 39
2 30 31
1 72
0
1 34
1 75
1 39
0
1 252
0
0
1 75
1 252
0
4 37 40 266 46
2 38 39
0
0
3 41 44 48
0
0
1 75
1 266
0
1 53
2 59 62
3 49 266 56
0
0
1 266
1 75
1 266
1 60
1 56...

output:

508 509
503 508
503 507
503 506
504 505
496 504
489 496
501 503
500 501
491 500
482 491
494 502
489 494
489 499
488 498
480 488
492 497
492 495
484 493
485 492
475 485
484 490
484 489
482 484
474 480
466 474
484 487
484 486
471 475
479 482
477 479
471 477
481 483
475 481
468 471
465 468
463 465
453 ...

result:

ok Accepted (100 test cases)

Test #9:

score: 0
Accepted
time: 24ms
memory: 7636kb

input:

5
4174
3 9 15 2088
3 3 18 7
0
2 23 12
1 15
2 19 2088
0
1 19
1 23
2 11 2088
3 16 17 21
0
1 20
2 2088 38
0
0
0
2 28 27
1 20
0
0
2 2088 39
1 34
2 30 47
1 30
2 29 2088
0
1 34
0
0
1 39
1 47
1 2088
0
1 39
1 51
2 2088 44
2 42 51
2 46 49
2 55 2088
1 42
0
1 44
0
1 55
0
2 48 52
0
0
2 2088 58
2 59 53
1 63
0
2 ...

output:

4171 4174
4163 4173
4171 4172
4162 4171
4154 4162
4148 4154
4160 4170
4163 4169
4162 4168
4164 4167
4160 4164
4156 4166
4158 4165
4155 4158
4159 4160
4155 4163
4149 4155
4151 4161
4156 4159
4152 4156
4150 4152
4143 4150
4153 4157
4151 4153
4139 4143
4137 4139
4148 4149
4149 4151
4133 4137
4140 4148
...

result:

ok Accepted (5 test cases)

Test #10:

score: 0
Accepted
time: 25ms
memory: 8004kb

input:

4
32538
4 21 46 18 16255
2 14 22
1 46
1 17
1 18
2 8 50
2 16 11
1 16
1 16255
1 50
0
2 20 22
1 18
1 17
2 16272 33
0
0
2 23 27
1 50
0
2 32 28
2 30 36
0
1 16272
3 26 38 37
0
0
0
1 50
0
1 16272
1 36
2 42 53
1 39
1 50
0
1 39
3 51 44 48
0
1 50
1 16272
1 55
1 62
0
2 16299 78
1 59
1 16299
0
1 59
2 56 67
1 55...

output:

32530 32538
32529 32537
32530 32536
32525 32535
32526 32534
32517 32526
32531 32533
32529 32531
32525 32532
32521 32529
32527 32530
32517 32527
32516 32521
32527 32528
32511 32517
32516 32525
32520 32524
32513 32520
32517 32523
32516 32522
32515 32516
32506 32513
32518 32519
32515 32518
32511 32515
...

result:

ok Accepted (4 test cases)

Test #11:

score: 0
Accepted
time: 23ms
memory: 8284kb

input:

3
54304
3 7 27151 13
1 7
3 11 8 27158
2 6 11
1 22
2 9 12
0
0
0
1 27158
3 14 17 31
0
2 25 22
2 15 23
0
1 25
0
1 31
1 27158
1 26
2 36 27158
3 27 28 34
0
1 40
1 26
0
0
0
1 36
2 27158 48
1 40
1 34
2 41 27158
0
1 41
0
5 27175 42 45 46 73
1 48
1 27175
0
0
0
2 52 58
1 27175
0
0
2 50 73
2 49 57
0
0
3 54 56 ...

output:

54301 54304
54301 54303
54292 54302
54293 54301
54291 54293
54284 54291
54294 54300
54289 54294
54290 54299
54288 54290
54293 54298
54292 54297
54295 54296
54289 54295
54288 54292
54284 54288
54286 54289
54282 54286
54281 54287
54279 54285
54282 54284
54278 54282
54275 54278
54267 54275
54281 54283
...

result:

ok Accepted (3 test cases)

Test #12:

score: 0
Accepted
time: 19ms
memory: 8784kb

input:

2
64362
6 2 13 32175 17 6 18
0
3 15 11 23
2 32175 14
1 17
0
1 15
1 11
1 18
2 32175 20
0
2 22 21
1 28
0
0
1 32175
2 22 24
0
1 32175
0
0
2 27 32
2 25 33
0
0
2 31 32175
0
1 33
2 36 40
1 36
1 36
0
0
3 32175 48 42
1 32175
2 37 46
0
1 40
2 56 45
0
1 56
0
3 32182 80 60
3 32182 52 53
0
0
1 80
1 57
2 32192 7...

output:

64354 64362
64355 64361
64354 64355
64351 64360
64350 64359
64350 64358
64351 64357
64348 64356
64341 64348
64345 64354
64337 64345
64346 64353
64346 64352
64342 64351
64342 64350
64339 64349
64339 64341
64338 64347
64345 64346
64328 64337
64320 64328
64319 64320
64312 64319
64342 64344
64341 64343
...

result:

ok Accepted (2 test cases)

Test #13:

score: 0
Accepted
time: 26ms
memory: 17604kb

input:

1
194798
3 2 3 97357
0
0
3 6 8 97357
1 6
0
2 16 32
1 24
3 97357 14 19
2 97357 13
2 97357 20
1 32
0
0
2 97357 29
2 28 26
1 97357
2 97357 27
0
0
1 29
1 37
1 97357
1 28
2 35 97357
0
0
0
0
1 35
4 33 34 97357 45
1 37
0
0
0
2 38 97357
0
0
3 97357 48 67
1 45
1 50
1 97357
2 97361 47
3 106 97382 59
1 50
1 48...

output:

194793 194798
194792 194793
194792 194797
194787 194796
194781 194787
194794 194795
194792 194794
194786 194792
194785 194786
194776 194785
194784 194791
194789 194790
194781 194789
194784 194788
194767 194776
194761 194767
194778 194784
194768 194778
194759 194768
194779 194783
194770 194779
194773...

result:

ok Accepted (1 test case)

Test #14:

score: 0
Accepted
time: 10ms
memory: 5680kb

input:

10000
8
2 2 5
3 8 6 7
1 5
1 8
0
0
0
0
8
4 3 4 8 7
1 5
1 5
0
0
1 8
0
0
4
2 2 4
0
1 4
0
3
2 2 3
0
0
2
1 2
0
12
1 4
4 3 8 10 6
0
2 7 11
1 10
0
0
2 9 12
0
0
1 12
0
6
2 3 5
2 6 4
1 6
0
0
0
4
1 3
1 4
1 4
0
7
2 3 7
1 5
2 4 6
0
1 6
0
0
14
4 2 13 5 7
2 4 6
1 13
2 8 14
2 9 11
2 10 12
0
0
0
0
0
0
0
0
4
2 4 3
1...

output:

4 8
2 4
2 7
2 6
3 5
1 3
1 2
6 8
1 6
1 7
3 5
2 3
1 4
1 2
3 4
1 3
1 2
1 3
1 2
1 2
11 12
8 11
4 8
5 10
2 5
8 9
2 4
4 7
2 6
1 2
2 3
3 6
2 3
1 5
2 4
1 2
3 4
2 3
1 2
1 7
5 6
3 5
2 3
3 4
1 2
4 14
3 13
1 3
6 12
5 11
6 10
5 9
4 8
1 7
2 6
1 5
2 4
1 2
2 4
1 2
1 3
1 4
2 3
1 2
7 10
5 7
2 9
1 8
4 5
1 4
2 6
2 3
1 ...

result:

ok Accepted (10000 test cases)

Test #15:

score: 0
Accepted
time: 15ms
memory: 5736kb

input:

10000
14
2 2 10
4 6 4 5 12
1 6
2 7 9
2 11 13
0
0
1 14
0
1 14
0
0
0
0
11
4 4 5 6 11
2 7 10
1 5
2 8 9
0
0
1 8
0
0
0
0
9
4 3 4 6 7
1 8
2 5 9
0
0
0
0
1 9
0
16
2 8 7
2 12 8
1 12
1 8
1 7
1 13
0
4 9 10 15 16
0
0
1 15
1 13
0
1 16
0
0
10
3 4 3 7
2 10 5
0
1 10
0
1 7
2 8 9
0
0
0
5
3 5 3 4
1 5
0
0
0
7
2 3 5
2 3...

output:

10 14
8 10
5 13
2 12
5 11
1 8
4 9
4 7
3 6
2 3
2 5
2 4
1 2
1 11
2 10
4 9
7 8
4 7
2 4
1 6
3 5
1 3
1 2
8 9
3 8
2 3
1 7
1 6
3 5
1 4
1 2
14 16
8 14
11 15
8 11
12 13
6 12
3 6
2 3
8 10
8 9
4 8
2 4
1 2
5 7
1 5
4 10
2 4
7 9
7 8
6 7
1 6
2 5
1 2
1 3
2 5
1 2
1 4
1 3
3 7
2 6
1 5
3 4
2 3
1 2
1 10
6 9
1 6
7 8
4 7
...

result:

ok Accepted (10000 test cases)

Test #16:

score: 0
Accepted
time: 17ms
memory: 5688kb

input:

10000
17
2 2 12
4 14 6 11 10
2 7 12
1 14
1 6
0
0
2 15 13
1 12
0
1 15
2 16 17
0
0
0
0
0
9
3 5 4 9
1 5
1 4
0
2 7 8
1 9
0
0
0
5
2 3 5
1 4
1 4
0
0
18
3 4 3 10
2 9 16
0
2 14 12
3 8 15 11
1 18
1 14
0
1 13
1 17
0
1 13
0
0
1 17
1 18
0
0
2
1 2
0
14
3 3 13 7
2 6 11
1 10
1 13
2 8 14
1 10
1 12
1 12
1 14
0
0
0
0...

output:

12 17
12 16
11 15
8 11
4 14
2 4
8 13
9 12
3 9
1 3
2 8
2 10
3 7
5 6
2 5
1 2
6 9
1 6
5 8
5 7
2 5
1 2
3 4
1 3
1 5
3 4
2 3
1 2
16 18
6 16
15 17
10 15
2 6
5 10
7 14
4 7
12 13
9 12
4 9
5 11
1 5
2 4
5 8
1 2
1 3
1 2
9 14
5 9
4 13
1 4
8 12
7 8
2 11
6 10
3 6
5 7
1 5
2 3
1 2
1 11
2 10
5 9
1 5
2 8
6 7
3 6
2 3
2...

result:

ok Accepted (10000 test cases)

Test #17:

score: 0
Accepted
time: 19ms
memory: 5584kb

input:

10000
12
3 3 6 11
2 9 7
1 9
1 12
1 7
1 12
0
1 10
1 10
0
0
0
9
4 7 5 6 9
1 7
1 8
1 5
0
0
1 8
0
0
16
3 5 3 6
3 4 7 12
0
0
2 7 11
0
3 9 15 13
1 11
0
1 15
0
2 14 16
0
0
0
0
13
1 3
3 4 8 10
4 6 7 9 12
2 5 6
0
2 11 13
0
0
0
0
0
0
0
4
2 4 3
1 4
0
0
8
2 5 3
2 6 7
0
1 6
1 8
1 8
0
0
20
2 7 6
3 4 10 11
2 13 8
...

output:

6 12
4 6
1 11
9 10
8 9
3 8
2 3
5 7
2 5
1 4
1 2
1 9
7 8
3 7
2 3
1 2
1 6
4 5
1 4
12 16
10 15
7 10
12 14
7 13
2 12
8 11
5 8
7 9
5 7
2 5
1 6
1 2
2 4
1 3
6 13
3 12
6 11
2 10
3 9
2 8
3 7
4 6
3 4
4 5
2 3
1 2
2 4
1 2
1 3
6 8
5 6
2 7
4 5
2 4
1 2
1 3
10 20
11 19
17 18
10 17
13 16
6 13
11 15
4 14
3 6
10 12
2 1...

result:

ok Accepted (10000 test cases)

Test #18:

score: 0
Accepted
time: 21ms
memory: 5624kb

input:

100000
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2
0
2
1 2...

output:

1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
...

result:

ok Accepted (100000 test cases)

Test #19:

score: 0
Accepted
time: 37ms
memory: 15836kb

input:

1
200000
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 66869
1 6...

output:

247 200000
303 199999
199997 199998
378 199997
399 199996
421 199995
423 199994
425 199993
445 199992
449 199991
450 199990
467 199989
199987 199988
473 199987
475 199986
199984 199985
485 199984
199982 199983
497 199982
516 199981
199979 199980
518 199979
538 199978
545 199977
199975 199976
545 199...

result:

ok Accepted (1 test case)

Test #20:

score: 0
Accepted
time: 36ms
memory: 20288kb

input:

1
200000
5703 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 1374 1375 1440 1486 1487 1488 1489 1845 1846 1847 1848 1849 1850 1851 1860 1861 1862 1863 1864 1865 1866 1867 1868 1888 1889 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330 3446 ...

output:

199907 200000
199907 199999
199907 199998
199907 199997
199907 199996
199907 199995
199907 199994
199907 199993
199907 199992
199907 199991
199907 199990
199907 199989
199907 199988
199907 199987
199907 199986
199907 199985
199907 199984
199907 199983
199907 199982
199907 199981
199907 199980
199907...

result:

ok Accepted (1 test case)

Test #21:

score: 0
Accepted
time: 44ms
memory: 16592kb

input:

1
200000
11 39 63012 63019 63148 63219 63220 63262 63263 130152 198563 199731
9 3 4 39 60342 60876 60977 62603 62911 62944
0
5 5 7 23 25 36
0
3 8 19 22
4 8 15 16 18
4 9 10 12 14
0
0
1 13
1 13
0
0
0
0
1 18
0
2 20 21
0
0
0
0
2 27 31
2 26 29
0
2 28 30
0
1 30
0
3 32 33 35
0
0
1 35
0
2 37 38
0
0
15 41 42...

output:

199999 200000
199997 199999
199957 199997
199997 199998
199994 199996
199994 199995
199957 199994
199957 199993
199991 199992
199957 199991
199977 199990
199988 199989
199977 199988
199977 199987
199985 199986
199977 199985
199977 199984
199978 199983
199980 199982
199980 199981
199979 199980
199978...

result:

ok Accepted (1 test case)

Test #22:

score: 0
Accepted
time: 34ms
memory: 13124kb

input:

2
100000
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 18907
1 1...

output:

165 100000
204 99999
254 99998
255 99997
255 99996
263 99995
290 99994
99992 99993
290 99992
305 99991
307 99990
321 99989
336 99988
99986 99987
99985 99986
343 99985
357 99984
99982 99983
99981 99982
376 99981
99979 99980
378 99979
387 99978
99976 99977
393 99976
414 99975
414 99974
418 99973
433 9...

result:

ok Accepted (2 test cases)

Test #23:

score: 0
Accepted
time: 30ms
memory: 13788kb

input:

2
100000
2810 2 3 4 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 951 952 953 1008 1009 1010 1019 1020 1021 1046 1047 1048 1049 1050 1581 1582 1583 1584 1585 1586 1587 1588 1589 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1680 1693 1694 1711 1712 1713 1732 1733 1951 1952 2040 20...

output:

1 100000
99815 99999
99815 99998
99815 99997
99815 99996
99815 99995
99815 99994
99815 99993
99815 99992
99815 99991
99815 99990
99815 99989
99815 99988
99815 99987
99815 99986
99815 99985
99815 99984
99815 99983
99815 99982
99815 99981
99815 99980
99815 99979
99815 99978
99815 99977
99815 99976
998...

result:

ok Accepted (2 test cases)

Extra Test:

score: 0
Extra Test Passed