1868. MinCut Query
#1868. MinCut Query
题目描述
有 N 个点 M 条边的无向带权图，求所有 s,t(s <t)，求出 s ， t 的最小割的容量(原题相当于这个意思)。
约束条件 ： 数据组数 _T ≤20 , N ≤150, M ≤3000 _
输入格式
输出格式
样例
样例输入
11
24 87
10 20 747794
8 11 760493
10 14 202363
20 3 520060
12 23 180541
19 5 455737
12 9 702568
22 15 21531
15 20 174068
8 18 979803
7 19 133070
16 2 18457
20 11 176230
24 9 898538
15 21 798316
19 6 803527
20 21 759957
10 15 999171
5 2 702306
22 21 336328
9 18 750847
10 2 925858
13 16 819583
10 15 233368
3 21 344044
15 8 426809
13 3 695789
1 4 502652
3 8 999933
13 21 993369
20 5 636227
19 7 297540
4 11 651435
11 12 66602
18 15 573318
13 5 260757
14 9 724287
2 10 429690
5 12 558441
10 16 108118
10 12 834482
12 22 698928
16 17 179498
10 19 276966
11 12 406220
9 17 332872
21 6 409504
12 7 363369
5 12 226341
22 13 700724
3 14 122847
4 2 243556
12 17 537765
21 2 792351
2 5 757035
5 13 324915
12 9 373744
4 12 148366
4 17 151433
24 6 899229
12 24 901475
2 3 794396
6 14 908236
2 3 894429
16 4 335929
10 9 322405
6 3 118607
11 1 670689
10 22 569918
13 21 987744
7 24 298491
12 5 206726
5 7 617506
12 3 469787
22 3 308543
9 14 939508
4 5 376349
12 15 127829
12 16 195747
9 5 755423
24 11 267606
2 14 473731
23 18 229321
9 5 248627
19 18 586709
17 19 213259
21 22 442063
5
8962600
6532036
8433452
3911899
1419379
31 269
3 9 487132
25 31 808934
25 5 370164
24 26 548900
1 30 713774
19 16 187191
23 29 116467
27 30 422091
26 15 855543
1 3 517446
27 6 418419
1 28 103349
5 20 262010
12 10 166343
21 10 319302
17 27 575322
20 21 229905
18 20 73941
30 23 346229
31 1 565985
3 16 789225
28 2 821397
16 21 740085
26 3 207673
2 12 905386
28 4 306641
13 23 340714
22 8 280525
23 4 108582
25 3 937733
19 5 218005
14 31 85274
14 15 247256
22 9 575580
18 11 223206
30 5 962505
26 15 262755
11 5 518945
13 26 723507
7 19 222843
30 4 235190
6 18 849959
13 29 518809
8 17 383304
11 9 999755
13 17 690369
28 16 238047
1 21 66250
26 29 3034
11 6 910254
15 19 519126
30 29 245976
27 23 703730
12 25 253415
13 2 26305
13 14 278051
7 10 308903
11 9 858700
28 1 132003
18 12 144501
6 24 908539
29 20 522536
1 15 171693
10 24 720505
22 6 590965
9 16 495344
14 22 202901
2 1 416950
7 27 717989
12 13 40744
20 17 658391
15 12 553542
6 10 174233
21 20 690361
25 8 266762
1 17 903191
20 28 806368
15 29 730691
18 5 226058
21 14 328206
3 2 947387
5 14 602727
27 20 56553
29 7 528947
24 1 756971
24 30 799632
6 16 418628
9 28 439215
11 14 720091
9 2 909611
16 2 152275
8 4 356621
9 28 77889
20 26 487771
29 22 372261
25 11 107206
8 26 648519
4 5 436874
18 19 967638
17 13 826608
18 6 149315
19 10 591101
16 3 89439
10 31 633075
25 26 933682
2 17 550271
14 24 101840
1 28 92623
29 12 319848
3 28 456683
22 12 745792
16 28 391522
18 12 631492
6 19 359232
29 5 614031
14 10 241082
7 4 33003
1 5 261797
12 19 974581
6 15 513971
15 13 235380
11 19 31537
21 27 433484
6 30 984858
16 27 469912
26 8 505237
15 12 675106
5 12 421245
20 21 519935
7 24 558956
14 5 343769
4 13 552806
10 2 876983
20 8 593094
10 21 186594
5 15 850544
6 30 734714
11 3 474763
18 22 32920
13 27 110295
19 9 760236
7 10 305154
14 19 666329
16 8 306711
14 15 836837
6 17 387091
5 23 714905
15 31 369634
3 16 613074
11 26 419806
9 13 336504
11 20 82196
26 2 721121
9 15 686764
28 26 963982
3 1 539037
26 3 433519
14 18 322533
2 18 627322
12 29 384173
14 6 152041
23 15 307399
10 7 370348
20 26 886060
13 18 626925
13 26 271233
13 26 630444
28 23 875641
15 2 250263
12 6 561042
15 24 208325
27 29 454155
2 1 937458
16 19 591172
22 31 725219
2 10 914654
5 22 53960
7 4 547085
6 29 742699
11 6 798899
4 2 825172
30 8 752507
30 28 178225
15 9 490001
14 7 945054
23 30 671339
14 15 28068
30 21 776788
31 27 292123
8 4 884851
30 7 202255
17 3 973814
6 31 199182
8 14 15721
29 28 590182
21 17 79297
14 30 138723
26 28 230298
9 25 443182
20 1 767058
3 31 860000
18 14 687484
10 19 68978
10 16 895022
4 13 508861
21 7 277686
19 15 590931
14 13 197315
5 1 95821
6 24 395529
3 23 897491
16 20 889619
2 18 80929
23 25 804311
11 29 634226
19 18 543438
8 3 107723
22 14 418658
11 19 689127
17 22 726652
25 24 140529
21 6 241889
23 5 928578
17 28 755200
26 7 126088
16 24 400658
11 31 377018
27 11 918185
14 29 55806
4 11 588955
25 10 19594
28 31 372556
2 4 806446
27 31 560998
31 26 466128
23 5 914694
22 18 987335
9 11 994986
4 24 691762
15 25 631542
19 16 711851
11 10 550400
24 11 801174
21 4 839852
11 4 488264
17 26 570038
1 15 28829
6 23 576988
20 25 578342
30 8 587666
18 27 149518
16 4 41352
9 27 706507
6 14 709365
2 25 434155
21 8 273680
14 8 292539
22 12 916171
9 29 62761
17 27 304466
18 14 713887
1 27 826970
25 5 532622
26 10 637290
28 9 734674
5 29 774549
3 12 704314
17 31 994950
18 9 157794
9
9588156
8400960
8982933
1098823
7323286
3213171
8275358
185677
5040140
6 182
6 3 150324
5 3 409955
4 5 322043
3 2 423920
6 5 293470
3 2 474977
2 6 63134
6 1 161957
2 4 953667
5 3 361730
1 3 88132
6 5 5217
2 5 434574
6 5 276126
6 4 312497
1 4 848154
1 4 843486
1 2 450031
4 6 206899
5 3 406425
2 1 411642
1 5 873481
3 6 628790
5 3 342724
3 2 152494
4 1 124221
6 1 49614
2 1 938271
4 6 96181
2 5 137089
6 1 979970
5 6 800031
2 4 620095
3 1 487331
5 2 231350
2 1 843882
4 3 874134
6 3 623288
4 5 495355
1 3 510140
4 2 677419
6 1 485270
6 5 342734
4 3 654820
2 4 100670
3 6 974803
2 1 598090
1 6 995961
3 2 402558
6 2 418817
1 6 571523
2 6 646580
4 1 273379
4 1 564046
3 2 804900
4 2 721387
2 3 966949
1 3 68507
2 3 665418
3 2 288821
6 3 86318
3 6 419018
2 4 712996
3 6 196296
2 6 264802
6 5 658926
6 3 613092
5 1 255813
1 5 362125
4 2 65187
4 5 56795
5 2 286142
5 6 482438
4 5 263591
6 5 226514
2 1 478258
5 6 352347
6 5 151226
6 3 36422
1 5 340635
1 2 120357
3 4 585473
1 6 568112
6 4 747662
6 3 470217
6 5 335345
5 1 846268
5 6 260758
2 3 194651
1 3 581877
2 3 963954
6 4 41599
6 4 714938
3 1 132541
3 6 720084
1 3 615610
3 5 22940
3 6 2607
5 4 52252
6 4 442531
2 5 953166
6 4 919592
6 2 568485
2 6 804920
3 4 815495
3 4 287640
4 5 851989
1 5 184681
5 1 993019
5 4 754099
6 3 976506
2 5 916067
5 4 571473
5 2 386967
4 5 224548
3 1 581087
1 4 989878
3 4 841198
3 6 162036
6 2 48499
6 5 713862
5 1 570004
4 3 564429
4 2 463634
2 5 880382
1 6 720898
3 6 602409
6 2 852635
5 3 808586
4 6 34987
3 5 237893
1 2 389570
1 6 596367
2 4 222834
5 1 73848
4 3 22301
1 5 960630
4 5 256509
4 3 230776
3 5 253541
3 5 506519
2 3 329500
5 6 33063
2 3 193843
2 1 618835
2 5 95816
5 1 194466
2 1 825362
5 6 705361
5 6 938621
4 2 22925
1 2 387709
1 3 753871
5 2 207467
4 3 472516
6 1 183333
5 1 8694
4 2 632855
3 5 571476
6 1 110752
6 2 14812
4 3 768682
6 2 492500
2 3 314108
1 2 865741
2 4 309588
4 5 458794
6 4 546621
3 2 657372
3 4 49765
2 4 825801
2 5 500336
6 3 617458
1 4 180530
2 3 785293
6 2 792350
2 1 782141
3 4 602256
4 1 172026
5 2 458261
5 3 562958
5 4 232984
1
8078721
27 198
11 24 433879
24 21 219171
18 4 11521
26 14 793661
2 24 912268
8 14 247036
25 12 428609
21 8 59896
6 13 141010
16 9 574888
2 3 794058
19 22 321930
6 8 631943
8 20 544210
23 9 144855
9 25 203760
9 23 341974
5 19 713172
25 13 651900
8 18 257756
25 8 528781
6 27 38321
3 12 506953
22 27 103808
3 22 572526
1 3 190159
23 20 59561
3 4 332974
5 15 263749
22 8 769410
18 19 101833
5 25 239834
14 16 526128
3 10 356632
3 13 848342
27 2 27459
6 24 64902
17 12 40927
4 16 700700
1 7 189563
8 11 42349
5 4 449808
9 25 880570
19 1 415140
20 15 38586
21 19 368543
6 5 241708
14 2 601486
2 4 545191
24 12 710648
24 9 870462
16 8 296631
13 25 845521
14 18 980539
17 11 600931
21 2 658095
3 22 138645
5 24 121785
8 26 376926
22 17 438549
10 13 251531
12 10 97052
14 17 77590
3 27 194873
26 7 632558
3 11 565221
7 23 687006
4 22 580283
12 3 135237
1 25 481885
2 20 792725
27 2 113237
16 22 337243
15 2 386024
22 2 762112
26 20 816261
10 16 149956
22 19 341090
5 3 583959
9 19 265376
11 9 714675
14 8 777378
2 24 917670
9 11 252834
3 21 736907
12 20 483317
5 18 387571
9 12 213487
23 16 946278
23 13 220436
9 23 834947
14 25 150213
21 27 19541
11 8 278675
13 10 728803
18 6 999243
8 10 71162
19 17 484170
23 3 481136
8 24 776181
19 9 785901
17 18 572997
5 23 794115
12 1 784417
10 26 511626
3 16 238503
6 23 352950
5 3 197236
11 25 987800
27 21 31503
25 12 393800
9 17 939014
2 21 503767
17 21 347195
23 3 435777
6 22 837210
26 16 834685
1 20 64836
20 3 679782
3 19 482363
9 16 826265
12 13 506854
22 14 390770
1 20 204106
22 15 951143
26 9 774566
6 7 157266
25 7 203108
2 15 363559
20 17 185161
3 14 895039
14 15 311797
4 9 8431
3 9 295408
22 4 473496
17 18 537968
11 12 760030
20 9 492632
22 27 933008
15 19 101663
26 10 30097
25 24 112111
25 16 803070
11 18 123091
1 12 419370
9 18 127683
10 1 634296
5 10 741188
23 4 62252
4 18 274724
14 4 690627
26 5 418326
9 20 980457
25 20 399827
7 10 43861
5 27 678156
9 25 935696
21 1 997947
27 7 758864
17 22 78409
9 12 159162
13 10 710556
15 7 349145
13 21 928292
9 27 703448
20 4 253682
10 1 315330
24 10 827835
12 25 126902
20 14 217044
14 23 997812
22 24 713257
21 1 615860
12 2 253511
23 10 680298
5 2 971925
2 11 964126
14 6 833556
12 22 782720
14 5 326645
25 15 29730
22 7 443371
11 21 238859
12 18 446287
21 13 873514
11 1 554422
11 5 550659
6 7 374730
11 23 46008
4 3 489211
18 4 502309
13 15 657903
7 11 58107
13 17 655805
25 1 29502
14 17 370449
7 2 871001
14 7 205109
2
2411556
2838287
29 329
29 14 211984
8 22 881424
12 28 594862
18 28 605808
11 13 110912
5 28 565745
19 18 967138
10 3 365761
5 16 189142
1 6 574883
4 26 449834
12 5 343445
1 8 411311
8 17 537284
8 27 835413
4 24 163043
16 13 861121
16 14 946551
1 18 720738
13 19 365915
19 20 900659
15 19 499282
22 28 209119
1 15 524764
27 6 951319
21 3 459971
25 9 452112
9 18 810013
27 5 357056
8 18 478980
13 7 567090
29 13 514996
8 26 874212
24 26 770712
10 16 535327
28 7 946633
25 24 251762
7 3 503442
11 21 992211
27 20 846895
19 24 543484
2 23 378338
3 23 999214
24 17 527999
1 18 358642
12 16 116036
26 3 300132
4 10 480710
19 12 317825
10 1 6072
10 19 728907
16 13 386990
27 15 28657
6 9 313971
2 9 833103
7 1 500839
10 5 802943
19 11 608489
22 21 922597
4 3 500114
11 15 403455
1 22 432111
27 22 262433
28 23 611887
11 14 632905
3 14 486947
7 10 787583
9 3 442044
1 26 747320
22 21 446677
14 21 28216
6 14 79270
28 18 256710
13 21 468233
18 2 313523
2 20 125414
3 20 868265
5 3 376251
22 8 171795
5 7 983805
7 20 199268
29 18 363194
20 8 822255
29 20 376851
12 8 564351
26 1 755149
17 4 217178
17 29 153955
9 14 321699
23 18 452471
1 16 15470
20 8 591441
24 19 121289
17 10 990817
1 21 69028
7 9 693060
3 26 68400
19 5 459968
29 14 120689
9 28 321677
24 28 220240
21 10 328243
7 5 241307
28 13 732494
3 13 786387
5 19 716510
16 21 164627
14 2 482650
12 22 563182
29 13 735659
27 20 510063
29 4 359555
25 28 330335
8 3 324636
12 27 387965
1 2 660704
13 15 1843
7 12 319301
20 13 757447
5 13 33622
12 2 46388
11 1 871044
16 25 969711
12 24 800871
9 6 418418
11 27 268825
13 11 283859
7 9 297894
12 20 875110
1 24 63047
3 7 343703
24 17 800097
12 4 544875
26 7 575261
14 15 84507
20 18 26235
19 1 451353
4 7 659819
29 10 420006
1 2 257693
13 5 392188
27 28 366257
5 2 506749
3 16 366797
9 10 586312
26 2 591003
18 24 879553
16 18 982347
25 2 960251
19 9 517554
1 13 61049
26 15 84149
24 5 293555
11 29 543364
12 6 108343
13 1 891255
12 17 34226
28 18 510828
17 26 28381
10 11 963291
23 18 599301
29 13 513991
25 2 282620
24 21 989694
21 7 661449
21 2 265588
22 24 261903
2 25 733607
27 1 487535
1 19 124047
18 12 757670
23 13 503158
16 24 243659
7 18 565484
13 16 575987
7 13 638369
19 5 251328
22 27 891467
21 24 43634
21 16 191795
6 26 939256
11 19 200708
11 5 744778
26 12 794894
3 16 506458
29 22 999961
10 4 471745
5 25 646712
25 16 552369
8 28 394661
9 25 473288
6 27 106688
23 29 488614
5 25 807125
18 27 874975
24 19 945230
14 20 67661
28 24 536874
3 12 570125
1 11 654946
6 12 948089
8 17 690869
19 10 935501
23 7 552959
18 25 498188
23 15 82200
13 1 619073
7 4 189197
28 15 360495
5 26 308583
4 13 515803
3 12 191615
20 28 615539
18 13 194529
5 9 928546
15 25 547248
29 19 358698
17 8 413003
29 19 816851
13 21 575206
23 3 495192
19 20 484489
3 24 488324
1 5 574359
4 16 279466
21 22 690121
28 13 977623
11 29 90058
17 28 718296
8 3 830541
2 17 803376
24 7 347224
29 1 811559
5 23 259317
29 26 308971
4 17 769973
4 15 903581
14 17 424539
2 5 343900
1 4 627020
20 6 465513
4 21 474918
8 20 849763
28 16 551296
15 8 901555
17 3 922257
3 6 644297
1 11 975430
19 13 779601
14 5 422716
13 21 800836
4 17 575806
15 5 678686
23 15 40882
1 29 228400
3 22 185890
1 21 530608
11 8 816216
15 20 962075
19 28 251305
5 3 6047
24 7 235707
8 29 59766
6 13 554530
1 26 740419
22 10 787378
24 9 119945
10 21 598371
20 19 366027
17 21 372073
3 19 607780
7 3 439260
6 8 417810
19 6 444982
20 6 475738
16 27 638021
7 13 423612
19 22 644816
12 5 691644
17 13 76781
9 7 214108
4 9 162290
4 26 410763
9 18 730117
6 7 306241
24 26 669742
7 25 669539
21 14 267706
25 22 748251
29 5 600868
15 18 386866
23 27 472059
19 25 89326
7 5 812680
6 29 908252
2 1 762698
26 4 870792
11 18 518733
24 19 738996
28 20 594815
25 5 690580
26 19 981338
1 8 682858
5 7 630846
14 12 401426
17 5 841747
6 2 951606
27 4 361874
15 27 4040
1 17 279778
14 12 133131
6 1 980109
25 1 654527
1 27 984241
19 11 207434
19 28 782070
20 25 73371
15 22 575024
28 7 21415
21 29 191006
5 13 625422
15 10 195177
14 5 888681
12 6 795258
17 16 243939
24 5 175680
7 16 836826
12 2 130873
28 29 543848
2
7040077
9847451
19 217
8 5 443438
2 18 449967
19 7 111022
15 14 272670
1 4 517876
8 17 871054
10 12 1926
13 5 545773
12 18 909577
12 16 62427
15 12 466290
12 15 93663
4 10 366333
8 13 524436
11 6 866393
5 19 949223
14 16 897005
15 12 698448
13 18 60909
9 12 126163
2 5 573033
12 16 322903
13 19 138327
5 4 812299
13 11 520499
9 16 583399
12 10 164577
8 2 807879
4 3 419678
3 7 992710
11 19 315613
4 16 970291
8 19 298942
1 8 819440
7 4 919190
18 10 600118
3 11 924348
17 3 801456
8 4 326573
12 6 647340
11 17 819520
4 2 520790
3 1 527250
10 14 705291
10 2 487784
16 17 320789
5 8 353697
4 13 196472
7 1 458925
9 11 714088
6 18 317566
3 2 891335
4 2 280397
3 8 488898
8 15 649293
8 11 926157
10 12 127368
6 13 646387
10 19 491978
2 9 984909
7 11 694997
15 13 467936
16 14 4341
4 5 762387
18 14 8217
7 1 91186
18 8 198953
6 3 268865
1 10 755631
13 16 730763
5 9 198698
1 19 719390
5 2 481777
19 15 489993
6 13 97530
18 5 625381
6 3 302721
10 5 588475
19 5 713081
16 15 477753
3 19 290177
16 1 914399
8 5 940458
19 10 539235
12 8 451504
16 19 733939
11 1 541653
7 3 254733
1 17 248837
3 16 539013
15 13 969763
17 11 358133
18 6 203166
16 13 980438
10 9 714376
6 5 148991
6 19 553147
8 19 682473
2 4 784083
7 8 579959
4 16 454444
18 2 173961
17 13 832039
7 3 546414
12 4 211757
15 4 764903
12 18 166930
3 13 777126
9 17 873436
9 10 844231
8 11 18191
8 14 154914
2 14 350311
4 18 399084
10 7 882410
6 7 846136
4 7 77592
16 18 365724
11 5 906198
1 6 717775
9 10 779466
19 12 29950
14 2 992957
9 16 210802
12 6 218398
15 11 321739
10 15 592009
7 8 639404
10 18 76586
3 19 357999
18 8 690307
3 7 661175
8 17 982354
16 6 218968
6 17 359470
18 12 418447
17 2 573925
19 6 947780
16 15 43726
10 18 17567
14 12 318985
4 15 173202
16 1 908521
18 15 267991
16 7 202789
13 6 776713
9 11 724492
2 3 768217
13 17 950305
11 10 988872
19 2 612982
13 5 460091
14 18 40703
12 16 15534
17 13 960412
12 3 780947
17 9 943990
14 7 863874
3 19 279371
19 7 228786
5 3 13538
7 16 932289
4 7 374772
14 18 359760
1 12 706182
10 4 522002
5 17 507193
7 12 66538
11 14 132348
7 14 107604
6 1 129794
2 9 128426
9 14 684113
4 13 255333
16 5 303316
3 14 658791
9 3 725328
15 6 440877
18 17 548481
4 17 194626
6 3 839404
11 17 523516
14 7 778848
7 12 598515
4 8 730759
14 19 668625
16 15 759634
9 7 315862
8 5 566093
18 8 40216
7 10 186873
6 1 864482
16 12 949154
15 18 147071
6 18 496586
2 12 988540
19 5 722173
2 13 376243
6 7 64092
10 15 462919
1 6 701149
17 7 979246
9 17 36190
5 1 691648
3 7 594216
12 10 165408
16 5 12586
7 6 691976
2 8 453811
17 18 772213
14 15 277487
15 12 647242
13 18 966150
2 3 948481
16 2 427398
8 13 411205
16 7 117185
1
5000093
28 328
25 22 74538
27 14 363102
8 3 640588
2 10 287829
25 6 770331
1 28 718811
25 19 662560
9 14 73765
20 6 707301
28 11 876648
15 7 920965
5 18 888838
2 25 439380
14 10 357510
22 6 71711
12 7 266067
3 15 199089
2 7 358826
24 18 738725
12 25 322270
28 14 727460
1 22 683191
14 4 557052
20 9 628763
15 27 894829
17 14 610269
3 20 485446
28 18 740801
18 14 376427
19 9 64663
28 8 665132
11 9 302121
26 6 324
25 9 147733
27 24 146291
19 24 456376
27 10 838180
9 22 386301
13 11 189498
19 13 924555
21 24 342790
8 7 107682
1 16 490592
24 12 50708
12 11 150255
27 13 353915
10 24 405280
13 4 605357
17 28 995155
15 1 396915
11 18 358699
1 12 138955
16 11 919534
27 2 847846
21 1 438800
6 23 486129
13 10 887990
16 3 676150
27 5 170160
17 20 588724
12 2 866430
14 2 251817
12 1 644147
5 27 87184
22 4 196828
9 21 176738
18 5 561928
11 4 552474
4 2 54526
4 19 16205
15 14 880686
28 11 215547
24 22 461367
2 26 488778
22 20 710873
13 12 527093
11 1 417141
18 11 459132
11 27 70393
8 2 351187
9 28 214780
10 12 536222
25 7 970819
23 21 921753
20 26 753220
20 22 904019
24 4 892984
20 5 91750
3 15 692820
28 7 382705
14 15 750129
14 8 694224
7 16 983158
6 11 744726
2 14 615167
1 18 274957
23 13 417184
18 17 636481
8 3 968967
23 2 469169
24 16 185995
8 13 483779
14 16 206372
24 22 746869
10 24 40585
11 20 238320
23 4 845389
11 20 544208
26 18 419495
27 11 193838
26 13 234661
10 11 486059
14 4 186432
7 9 346277
3 13 160559
6 24 162946
9 25 787892
12 16 961689
4 8 22299
13 20 256959
7 3 743017
3 11 979983
18 26 196229
26 23 39627
11 13 268781
6 26 333577
14 6 870497
2 10 848506
27 25 253125
18 22 270348
20 28 900306
5 2 721064
3 19 760958
19 1 630776
10 23 177504
6 12 403530
22 26 901095
6 11 876700
15 9 49677
19 10 549110
27 14 509193
8 18 619042
12 4 355904
13 22 911192
20 3 550
11 20 126998
12 14 122591
6 3 396297
6 2 743873
14 20 187619
15 2 500844
15 22 942917
28 5 977468
3 1 833429
19 4 517724
12 26 331835
5 10 609340
7 27 220735
19 4 14524
8 1 760183
22 15 728061
21 13 334814
21 12 817858
8 15 938150
16 17 842817
11 28 709362
26 17 457667
9 7 505178
23 10 244945
22 17 726646
25 10 532092
17 14 654125
14 18 744488
27 25 126382
14 24 907527
26 21 406848
26 12 548212
4 17 910311
13 21 286932
13 26 940088
6 18 837656
19 6 586389
8 5 152979
16 3 174070
12 28 554329
2 9 127598
17 6 674885
12 22 243701
14 18 57461
22 3 114219
25 8 219420
1 27 495097
17 18 515261
16 18 661807
9 1 101111
26 14 170115
19 2 117793
23 25 711382
15 11 116331
11 16 672877
5 12 534605
28 24 267403
12 13 210620
1 12 487237
3 20 353645
5 17 750074
16 19 599723
16 13 934452
9 11 180922
19 6 626065
4 10 242672
8 22 868400
10 5 605988
13 17 608415
18 20 566102
10 8 549731
28 7 686897
2 22 168838
17 14 755604
10 5 21009
18 20 595623
10 11 215216
9 4 374884
20 16 589889
14 17 554740
11 27 854195
25 10 174722
2 23 150463
19 24 492801
2 5 350769
19 23 397244
1 16 166830
16 24 443281
7 15 437216
27 12 635873
10 22 909247
1 19 523764
26 4 79146
28 6 26197
28 7 62190
4 9 296836
23 21 5511
12 8 572966
4 15 572484
24 13 161535
16 23 873516
6 7 774510
17 16 67765
22 27 438470
7 27 609525
24 14 667345
7 9 691202
17 20 412661
22 8 722959
25 15 695632
11 2 918122
2 7 244624
12 7 333507
24 12 851585
14 18 808011
10 13 37201
10 3 969101
19 3 737836
7 6 753684
21 5 414866
28 12 359265
11 18 692771
18 2 60708
3 19 868718
24 16 905918
6 2 875018
24 5 129206
15 12 464948
21 28 148633
9 25 533462
15 8 463646
3 2 725395
14 20 765828
5 22 509203
14 18 458318
12 23 445511
5 2 308631
26 1 425787
26 5 812978
18 13 131386
15 27 915710
24 14 475155
7 27 252102
18 15 61992
4 12 911549
17 23 925787
4 12 437272
22 9 740288
8 18 786668
21 7 772933
3 22 846427
16 1 850064
18 7 509318
8 9 368544
19 24 812812
19 25 264390
25 28 598297
16 5 976442
20 13 863771
15 5 408918
23 19 178047
26 6 118451
1 8 988230
27 15 36858
26 5 289889
9 7 721993
27 15 295032
11 14 801285
4 5 699241
27 20 801877
16 26 756932
22 23 963761
28 8 446576
13 6 424774
6 15 509402
7 8 95656
3 18 625674
27 28 53080
11 16 118160
19 14 607583
3 13 326985
18 6 90087
23 17 296010
6
3235673
5937718
1415411
5867970
7383757
9924812
29 89
2 22 940702
18 5 430645
14 26 409560
24 25 224865
4 28 834533
17 25 900258
2 11 56843
25 21 292516
17 10 676838
8 29 983347
4 22 450386
8 10 405691
17 22 244507
4 13 734877
2 13 35880
18 5 459673
20 7 179475
4 7 353348
13 1 910978
4 25 948248
25 20 442571
27 11 367539
13 19 218418
2 26 86682
6 10 50741
11 16 614418
9 26 801056
16 14 477010
8 2 632499
3 21 255289
14 11 56928
15 26 156976
28 10 967488
12 26 745798
22 4 876568
22 29 677623
8 6 670984
19 6 640095
21 7 385038
17 11 78593
26 17 431239
13 20 511560
23 4 779228
3 25 930068
1 25 317429
4 2 335936
4 24 482893
1 8 168165
29 21 275644
5 8 56449
8 5 804742
19 9 757663
17 23 511942
27 26 498981
21 18 408183
19 21 798384
16 17 81199
2 9 520461
29 9 605207
14 29 701747
10 15 973704
10 29 789924
4 8 385372
21 4 910887
9 3 270182
21 17 481765
29 3 176240
9 18 38880
9 16 177162
13 1 888245
25 2 404070
18 12 193909
28 7 495689
13 9 69233
7 9 210981
15 17 411261
18 17 398760
27 17 1512
14 22 497995
6 17 696225
28 27 868157
2 7 346365
6 5 262459
6 2 800554
7 4 862328
15 5 45330
23 14 870020
11 23 941605
24 15 476661
1
3810686
40 0
1
0
40 39
1 2 1
2 3 2
3 4 3
4 5 4
5 6 5
6 7 6
7 8 7
8 9 8
9 10 9
10 11 10
11 12 11
12 13 12
13 14 13
14 15 14
15 16 15
16 17 16
17 18 17
18 19 18
19 20 19
20 21 20
21 22 21
22 23 22
23 24 23
24 25 24
25 26 25
26 27 26
27 28 27
28 29 28
29 30 29
30 31 30
31 32 31
32 33 32
33 34 33
34 35 34
35 36 35
36 37 36
37 38 37
38 39 38
39 40 39
1
20
6 9
1 2 1
1 3 7
2 3 1
2 4 3
2 5 2
3 5 4
4 5 1
4 6 6
5 6 2
1
6
样例输出
276
276
276
248
66
437
374
420
0
212
0
345
0
0
0
0
0
55
175
0
0
27
0
27
27
147
385
780
590
12