QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#592080	#7181. Graph Cuts	phuong2222	WA	313ms	32688kb	C++14	5.9kb	2024-09-26 20:33:51	2024-09-26 20:33:52

Judging History

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

[2024-09-26 20:33:52]
评测

测评结果：WA
用时：313ms
内存：32688kb

查看

[2024-09-26 20:33:51]
提交

answer

#include<bits/stdc++.h>
using namespace std;
using lli = long long;
const int maxN = 2e5 + 5;
const int maxB = 448;
const int maxB1 = 448;
vector<int> type1,type0,adj[maxN];
int type[maxN],deg[maxN],n,m,val[maxN],l[maxB1],r[maxB1],id[maxN];
int sum0[maxB1],val0[maxN],id0[maxN];
int val1[maxN],id1[maxN],id11[maxN];
int id01[maxB1][maxN],sum01[2][maxB1][maxB1],sumch[2][maxB1],val01[2][maxB1][maxN];
int del[maxN];
vector<int> type01[maxB1],vex1;
struct Tedge
{
    int x,y;
}
e[maxN];
void presolve()
{
    int cntb = 0;
    for (int i = 0;i < maxN;++i)
    {
        if (i % maxB == 0) l[++cntb] = i;
        if (i % maxB == (maxB - 1)) r[cntb] = i;
        id[i] = cntb;
        //cerr << id[i] << "\n";
    }
}
void finddata()
{
    for (int i = 1;i <= n;++i)
    {
        type[i] = deg[i] > maxB;
        if (type[i])
        {
            id11[i] = vex1.size();
            vex1.push_back(i);
        }
    }
    for (int i = 1;i <= m;++i)
    {
        if (type[e[i].x] && type[e[i].y])
        {
            id1[i] = type1.size();
            type1.push_back(i);
        }
        if (type[e[i].x] == 0 && type[e[i].y] == 0)
        {
            id0[i] = type0.size();
            type0.push_back(i);
        }
    }
    for (int i = 1;i <= m;++i)
    {
        if (type[e[i].x] && !type[e[i].y])
        {
            id01[id11[e[i].x]][e[i].y] = type01[id11[e[i].x]].size();
            val01[1][id11[e[i].x]][type01[id11[e[i].x]].size()] = 1;
            sum01[1][id11[e[i].x]][id[type01[id11[e[i].x]].size()]]++;
            sumch[1][id11[e[i].x]]++;
            type01[id11[e[i].x]].push_back(i);
        }
        if (type[e[i].y] && !type[e[i].x])
        {
            id01[id11[e[i].y]][e[i].x] = type01[id11[e[i].y]].size();
            val01[1][id11[e[i].y]][type01[id11[e[i].y]].size()] = 1;
            sum01[1][id11[e[i].y]][id[type01[id11[e[i].y]].size()]]++;
            sumch[1][id11[e[i].y]]++;
            type01[id11[e[i].y]].push_back(i);
        }

    }
}
void input()
{
    cin >> n >> m;
    fill(deg + 1,deg + n + 1,0);
    fill(val + 1,val + n + 1,0);
    fill(id0 + 1,id0 + n + 1,-1);
    for (int i = 1;i <= m;++i)
    {
        cin >> e[i].x >> e[i].y;
        deg[e[i].x]++;deg[e[i].y]++;
        adj[e[i].x].push_back(i);
        adj[e[i].y].push_back(i);
    }
    presolve();
    finddata();
}
void query()
{
    for (int i : type1)
        if (val1[id1[i]] == 1 && del[i] == 0)
        {
            del[i] = 1;
            cout << i << "\n";
            return;
        }
    int cntb = (type0.size() + maxB - 1) / maxB;
    //cout << cntb << "A\n";
    for (int idb = 1;idb <= cntb;++idb)
    {

        if (sum0[idb] > 0)
        {
            for (int i = l[idb];i <= min(r[idb],int(type0.size()));++i)
                if (val0[i] == 1)
                {
                    del[type0[i]] = 1;
                    val0[i] = 0;
                    sum0[idb]--;
                    cout << type0[i] << "\n";
                    return;
                }
        }
    }
    for (int u : vex1)
    {
        if (sumch[val[u]][id11[u]] > 0)
        {
            int cntb = (type01[id11[u]].size() + maxB - 1) / maxB;
            for (int idb = 1;idb <= cntb;++idb)
            {
                if (sum01[val[u]][id11[u]][idb] > 0)
                {
                    for (int i = l[idb];i <= min(r[idb],int(type01[id11[u]].size()));++i)
                        if (val01[val[u]][id11[u]][i] == 1)
                        {
                            del[type01[id11[u]][i]] = 1;
                            val01[0][id11[u]][i] = 0;
                            val01[1][id11[u]][i] = 0;
                            cout << type01[id11[u]][i] << "\n";
                            return;
                        }
                }
            }
        }
    }
    cout << 0 << "\n";
}
void update(int u)
{
    //cerr << u << "a\n";
    val[u] ^= 1;
    if (type[u])
    {
        for (int i : type1)
            if (e[i].x == u || e[i].y == u) val1[id1[i]] ^= 1;
    }
    else
    {
        for (int i : adj[u])
        {

            if (del[i] == 1) continue;
            int v = e[i].x + e[i].y - u;
            if (!type[v])
            {
                val0[id0[i]] = (val0[id0[i]] ^ 1);
                if (val0[id0[i]] == 1) sum0[id[id0[i]]]++;
                else sum0[id[id0[i]]]--;
                //cout << sum0[id[id0[i]]] << "\n";
            }
            else
            {
                val01[1][id11[e[i].x]][id01[id11[e[i].x]][u]] ^= 1;
                val01[0][id11[e[i].x]][id01[id11[e[i].x]][u]] ^= 1;
                if (val01[1][id11[e[i].x]][id01[id11[e[i].x]][u]] == 1)
                {
                    sum01[1][id11[e[i].x]][id[id01[id11[e[i].x]][u]]]++;
                    sumch[1][id11[e[i].x]]++;
                }
                else
                {
                    sum01[1][id11[e[i].x]][id[id01[id11[e[i].x]][u]]]--;
                    sumch[1][id11[e[i].x]]--;
                }
                if (val01[0][id11[e[i].x]][id01[id11[e[i].x]][u]] == 1)
                {
                    sum01[0][id11[e[i].x]][id[id01[id11[e[i].x]][u]]]++;
                    sumch[0][id11[e[i].x]]++;
                }
                else
                {
                    sum01[0][id11[e[i].x]][id[id01[id11[e[i].x]][u]]]--;
                    sumch[0][id11[e[i].x]]--;
                }
            }
        }
    }
}
void solve()
{
    int q;
    cin >> q;
    while (q--)
    {
        char c;
        int u;
        cin >> c;
        if (c == '+' || c == '-') {cin >> u;update(u);}
        else query();
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("C.inp","r",stdin);
//    freopen("C.out","w",stdout);
    input();
    solve();
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 15400kb

input:

output:

result:

ok q=10

Test #2:

score: 0

Accepted

time: 3ms

memory: 14148kb

input:

0 0
0

output:

result:

ok q=0

Test #3:

score: 0

Accepted

time: 2ms

memory: 13752kb

input:

0 0
1
?

output:

result:

ok q=1

Test #4:

score: 0

Accepted

time: 10ms

memory: 15644kb

input:

output:

result:

ok q=100000

Test #5:

score: 0

Accepted

time: 218ms

memory: 17704kb

input:

output:

result:

ok q=100000

Test #6:

score: 0

Accepted

time: 167ms

memory: 17056kb

input:

output:

result:

ok q=100000

Test #7:

score: 0

Accepted

time: 129ms

memory: 17532kb

input:

output:

result:

ok q=100000

Test #8:

score: 0

Accepted

time: 93ms

memory: 17740kb

input:

output:

result:

ok q=100000

Test #9:

score: 0

Accepted

time: 68ms

memory: 17712kb

input:

output:

result:

ok q=100000

Test #10:

score: 0

Accepted

time: 37ms

memory: 17468kb

input:

output:

result:

ok q=100000

Test #11:

score: 0

Accepted

time: 24ms

memory: 17292kb

input:

output:

result:

ok q=100000

Test #12:

score: 0

Accepted

time: 215ms

memory: 17692kb

input:

output:

result:

ok q=100000

Test #13:

score: 0

Accepted

time: 171ms

memory: 17724kb

input:

output:

result:

ok q=100000

Test #14:

score: 0

Accepted

time: 134ms

memory: 17308kb

input:

output:

result:

ok q=100000

Test #15:

score: 0

Accepted

time: 92ms

memory: 16940kb

input:

output:

result:

ok q=100000

Test #16:

score: 0

Accepted

time: 62ms

memory: 16752kb

input:

output:

result:

ok q=100000

Test #17:

score: 0

Accepted

time: 43ms

memory: 17692kb

input:

output:

result:

ok q=100000

Test #18:

score: 0

Accepted

time: 30ms

memory: 16984kb

input:

output:

result:

ok q=100000

Test #19:

score: 0

Accepted

time: 224ms

memory: 17700kb

input:

output:

result:

ok q=100000

Test #20:

score: 0

Accepted

time: 155ms

memory: 16792kb

input:

output:

result:

ok q=100000

Test #21:

score: 0

Accepted

time: 171ms

memory: 17528kb

input:

output:

result:

ok q=100000

Test #22:

score: 0

Accepted

time: 117ms

memory: 17136kb

input:

output:

result:

ok q=100000

Test #23:

score: 0

Accepted

time: 71ms

memory: 16824kb

input:

output:

result:

ok q=100000

Test #24:

score: 0

Accepted

time: 48ms

memory: 17724kb

input:

output:

result:

ok q=100000

Test #25:

score: 0

Accepted

time: 21ms

memory: 17288kb

input:

output:

result:

ok q=100000

Test #26:

score: 0

Accepted

time: 220ms

memory: 17500kb

input:

output:

result:

ok q=100000

Test #27:

score: 0

Accepted

time: 165ms

memory: 16828kb

input:

output:

result:

ok q=100000

Test #28:

score: 0

Accepted

time: 130ms

memory: 16952kb

input:

output:

result:

ok q=100000

Test #29:

score: 0

Accepted

time: 101ms

memory: 17744kb

input:

output:

result:

ok q=100000

Test #30:

score: 0

Accepted

time: 68ms

memory: 17168kb

input:

output:

result:

ok q=100000

Test #31:

score: 0

Accepted

time: 43ms

memory: 17680kb

input:

output:

result:

ok q=100000

Test #32:

score: 0

Accepted

time: 24ms

memory: 16768kb

input:

output:

result:

ok q=100000

Test #33:

score: 0

Accepted

time: 219ms

memory: 17808kb

input:

output:

result:

ok q=100000

Test #34:

score: 0

Accepted

time: 171ms

memory: 17664kb

input:

output:

result:

ok q=100000

Test #35:

score: 0

Accepted

time: 128ms

memory: 16868kb

input:

output:

result:

ok q=100000

Test #36:

score: 0

Accepted

time: 86ms

memory: 16464kb

input:

output:

result:

ok q=100000

Test #37:

score: 0

Accepted

time: 70ms

memory: 17276kb

input:

output:

result:

ok q=100000

Test #38:

score: 0

Accepted

time: 43ms

memory: 16936kb

input:

output:

result:

ok q=100000

Test #39:

score: 0

Accepted

time: 25ms

memory: 17756kb

input:

output:

result:

ok q=100000

Test #40:

score: 0

Accepted

time: 193ms

memory: 16608kb

input:

output:

result:

ok q=100000

Test #41:

score: 0

Accepted

time: 167ms

memory: 16844kb

input:

output:

result:

ok q=100000

Test #42:

score: 0

Accepted

time: 129ms

memory: 17804kb

input:

output:

result:

ok q=100000

Test #43:

score: 0

Accepted

time: 85ms

memory: 17168kb

input:

output:

result:

ok q=100000

Test #44:

score: 0

Accepted

time: 70ms

memory: 17028kb

input:

output:

result:

ok q=100000

Test #45:

score: 0

Accepted

time: 51ms

memory: 17732kb

input:

output:

result:

ok q=100000

Test #46:

score: 0

Accepted

time: 21ms

memory: 17804kb

input:

output:

result:

ok q=100000

Test #47:

score: 0

Accepted

time: 31ms

memory: 19224kb

input:

100000 100000
5722 1
35633 1
76503 1
2 8454
2 93428
3 91414
4 55025
21132 5
6 22400
6 80941
7 22043
7 29361
7 73158
78568 7
8 24159
8 26175
27612 9
39375 9
5454 10
24262 10
40601 10
11 8620
59525 11
11 79781
11 92891
64034 12
33728 14
14 59378
14 79826
560 16
16 31445
35262 16
17911 17
28509 17
9364...

output:

result:

ok q=100000

Test #48:

score: 0

Accepted

time: 31ms

memory: 19080kb

input:

100000 100000
32763 1
1 41318
52251 1
66464 2
83572 2
67186 5
7 64990
34545 8
8 96178
8628 9
10 8181
94794 15
16 33467
16 34451
85594 16
17 20413
31799 17
17 41753
18 61787
71853 18
19 5788
19 49136
97968 19
34661 20
20 61751
95244 20
20211 21
31082 21
22 96882
53538 23
53831 24
81268 24
25 52202
61...

output:

result:

ok q=100000

Test #49:

score: 0

Accepted

time: 31ms

memory: 19540kb

input:

100000 100000
98 1
1 39536
2 7197
2 36925
64304 2
3 90981
4 55694
4 58594
6 14112
6 61223
49657 7
49961 8
9 63064
84290 9
9616 10
10 26834
10 81424
11 28592
66665 11
11 67518
12 65671
12 77007
13 83518
88724 13
14 22525
28934 14
38904 15
18454 16
16 34371
33103 17
63576 17
46939 18
67514 18
18 72374...

output:

result:

ok q=100000

Test #50:

score: 0

Accepted

time: 34ms

memory: 18872kb

input:

100000 100000
1 30554
51310 1
1 71883
94585 1
2 40250
59351 2
2 60517
72989 3
4 3248
14035 4
4 90751
5 786
6 10125
87221 6
22862 7
7 57323
67940 7
40455 8
8 66854
9 34854
9 87440
43694 10
10 57462
82982 10
94968 10
47934 11
11 71829
24007 12
44565 12
48286 12
70260 12
12 70368
98761 12
20547 14
7549...

output:

result:

ok q=100000

Test #51:

score: 0

Accepted

time: 27ms

memory: 18828kb

input:

100000 100000
26140 1
46196 2
2 54845
78912 3
3 90871
4 12358
5 33609
5 43410
5 78393
47818 6
7 48862
13216 8
8 36636
8 40979
52931 8
8 80000
94821 8
52306 10
14072 12
36807 12
66342 12
344 13
13 4469
13 14570
13 52573
15 29037
15 38532
86576 15
16 9718
43023 16
16 86523
19 16448
20 15703
20 62471
8...

output:

result:

ok q=100000

Test #52:

score: 0

Accepted

time: 31ms

memory: 19588kb

input:

100000 100000
2005 1
1 15170
57799 2
4 38977
4 57240
42542 5
5 53318
5 75678
6 88650
65147 7
8 53626
8 70633
22352 10
11 49862
12 14548
12 50661
12 69416
13 22675
13 57792
3230 14
61629 16
16 94304
19 4752
11292 19
19 23963
47970 19
3280 20
20 13431
37640 20
20 43437
22 59910
69629 22
94875 22
23 52...

output:

result:

ok q=100000

Test #53:

score: 0

Accepted

time: 37ms

memory: 19624kb

input:

100000 100000
40394 1
75982 2
3 18844
73366 3
88698 3
4020 6
6 73638
7 22013
65853 7
8 75952
8 91846
8 92431
35947 9
25852 10
60988 10
84698 10
49696 11
60792 11
94447 12
29797 13
14 32289
14 45866
85823 14
15 5953
19579 15
9976 16
16 26641
17 70399
80811 17
18 57277
19 24826
19 72978
15405 20
64474...

output:

result:

ok q=100000

Test #54:

score: 0

Accepted

time: 32ms

memory: 19440kb

input:

100000 100000
1 46719
1 85926
2 31507
3 10325
25701 3
4 20660
4 24390
5 28826
5 32895
5 65707
5 85849
26769 6
35848 6
8 31592
9 6175
10 10273
10 49762
8543 11
12 1257
12 49533
67310 12
12 85402
4042 13
13 91901
14 36759
95374 14
40235 16
16 95131
17 47185
49412 17
86267 17
30733 18
19 36525
99630 20...

output:

result:

ok q=100000

Test #55:

score: 0

Accepted

time: 29ms

memory: 19280kb

input:

100000 100000
1 14816
1 36843
1 67254
69974 1
3 22460
4 94861
51245 5
5 53683
54692 6
6 91387
6 91712
8 56288
8 88631
9 4475
23107 9
9 37340
18545 10
10 32507
10 37510
86500 10
57406 11
11 96238
486 12
12 44026
51175 13
14 92685
14 94886
14 99844
66818 15
58293 16
16 92531
17 32186
36963 18
18 53409...

output:

result:

ok q=100000

Test #56:

score: 0

Accepted

time: 36ms

memory: 19460kb

input:

100000 100000
1 92961
32241 2
2 81221
4608 3
16927 3
18769 3
3 43374
22317 4
55044 4
18810 5
6 72739
61007 7
9 25577
9 27864
34366 9
10 16913
30734 10
40980 10
60805 10
74697 10
82279 10
10021 11
23696 12
36468 12
51197 12
86124 12
12 89628
14 6535
14 21742
14 36158
57841 14
15 81216
15 84873
16 457...

output:

result:

ok q=100000

Test #57:

score: 0

Accepted

time: 31ms

memory: 19120kb

input:

100000 100000
1 27333
1 84324
96084 1
9114 2
85952 2
3 5372
4 6733
9091 4
58622 4
4 86657
14441 5
55881 5
77265 5
5 80838
6 348
8 52617
8 61683
11583 9
9 73540
93581 9
94661 9
9 98721
46654 10
10 52226
12 55380
12 79729
13 40841
13 58505
80468 13
57058 14
14 59095
23508 15
68757 15
6286 17
17 39373
...

output:

result:

ok q=100000

Test #58:

score: 0

Accepted

time: 34ms

memory: 18828kb

input:

100000 100000
60818 1
1 61357
77477 1
3 45025
59533 3
46950 4
78991 4
97104 4
36194 5
6 64485
1740 7
5623 8
23553 8
16292 9
62566 9
9 98158
10 23566
10 47129
84382 10
10 89508
11 12522
54918 11
82691 14
89591 14
15 22620
22939 16
56415 16
16 83923
18 29619
18 83502
19 24669
79130 19
43646 20
21 6966...

output:

result:

ok q=100000

Test #59:

score: 0

Accepted

time: 32ms

memory: 18760kb

input:

100000 100000
34616 1
58002 1
1 70045
10303 2
2 39631
40632 2
10056 3
41853 3
70173 3
4 92959
5 47483
16468 6
50684 6
67732 6
84535 7
47014 8
59046 9
10 65208
10 78362
11266 11
24545 11
12 21449
66415 12
92002 12
13 19643
13 23316
96267 14
91298 15
17801 16
49544 16
69757 16
4694 17
17 24548
221 18
...

output:

result:

ok q=100000

Test #60:

score: 0

Accepted

time: 40ms

memory: 19512kb

input:

100000 100000
1 14279
25034 1
1 25644
1 33907
55554 1
32635 2
48898 2
67742 2
30821 3
62159 3
62878 4
4 99567
5427 5
81073 5
40389 6
68943 6
86783 6
7 7357
8 43901
8 49165
66447 8
15193 10
10 27651
52896 10
11 21927
31071 11
65058 11
1885 12
12 86604
13 34951
13 57211
73415 13
76672 13
31146 14
4934...

output:

result:

ok q=100000

Test #61:

score: 0

Accepted

time: 36ms

memory: 19592kb

input:

100000 100000
36686 1
2 28317
3 43331
58975 3
9005 5
5 38587
85424 5
87253 5
91242 6
7 12636
7 28747
43112 7
56525 7
95056 7
8 67866
8 96414
15486 9
9 17569
9 27913
9 45216
57385 9
12037 10
10 26847
68194 10
10 69558
91082 10
1181 11
29864 11
11 51315
74564 11
11 99360
50347 12
12 70424
80616 12
810...

output:

result:

ok q=100000

Test #62:

score: 0

Accepted

time: 35ms

memory: 19676kb

input:

100000 100000
19575 1
26203 1
72508 1
1 97963
14667 2
16976 2
3 6175
3 67390
3 85817
3 95274
61098 4
5 63076
48837 6
6 85456
8 11139
8053 9
9 14304
9 42080
78302 9
87001 9
95714 9
10 11640
10 38250
11 68261
33284 12
34067 13
37576 13
13 83578
15 23823
35578 16
57809 16
17 35284
43161 17
17 47477
516...

output:

result:

ok q=100000

Test #63:

score: 0

Accepted

time: 37ms

memory: 18668kb

input:

100000 100000
36059 1
46485 1
23653 2
73424 2
2 74494
51828 3
4 33328
53661 4
34793 5
6 51871
55444 6
6 65656
8 16246
8 34477
10425 9
62445 9
21534 10
10 30313
60761 10
96061 10
7597 11
11 15469
63367 12
40382 13
14 75126
15 56288
15 84929
53927 16
64468 16
17 53139
18 5845
76176 18
19 24677
19 5891...

output:

result:

ok q=100000

Test #64:

score: 0

Accepted

time: 32ms

memory: 19572kb

input:

100000 100000
20177 2
2 98955
3 46743
3 46866
62628 3
12631 4
75181 4
5 54593
27546 6
6 31901
6 83336
6 90688
7 32220
7 63366
8 61776
37721 9
9 48206
9 70008
96585 9
10 62990
98079 10
11 11607
21944 11
11 80964
13 9208
13 49235
13 69968
13 85800
38176 14
57272 14
15 3765
16 67576
17 40546
17 44435
1...

output:

result:

ok q=100000

Test #65:

score: 0

Accepted

time: 36ms

memory: 18952kb

input:

100000 100000
1 33218
2 26924
4 22063
4 72727
83189 4
5 26165
50928 5
6 12110
17480 7
39161 7
7 76692
20436 8
36025 8
9 52297
9 58874
67940 9
10 17168
10 40179
10665 11
11 26766
11 26798
28558 11
41443 11
91932 11
11 96520
12 38384
89050 13
14 44040
14 60933
63286 14
14 91796
38298 15
83369 15
20977...

output:

result:

ok q=100000

Test #66:

score: 0

Accepted

time: 31ms

memory: 19592kb

input:

100000 100000
97038 1
2 12394
73478 2
27345 3
3 52828
3 94198
17649 4
34700 4
4 48092
90308 4
4 92571
5 73178
5 96066
1197 6
79796 6
6 95080
7 6897
7 96564
8 57604
8 70048
29738 10
10 42975
10 99064
11 20156
11 25952
51206 11
11 97949
38714 12
92965 12
10950 13
15 6617
8272 15
17383 15
37580 15
5035...

output:

result:

ok q=100000

Test #67:

score: 0

Accepted

time: 33ms

memory: 18564kb

input:

100000 100000
1 43054
1 66061
45045 4
81759 5
15827 6
6 40801
78430 6
6 83704
3488 9
32237 9
10 8261
10 37635
98555 10
82566 11
30294 12
68894 12
13 32989
92708 14
94972 14
15 41948
16 28327
20490 17
52712 17
18 23230
18 77251
9533 19
66382 19
20 10583
23214 22
32369 22
24 32167
75443 24
26 9052
278...

output:

result:

ok q=100000

Test #68:

score: 0

Accepted

time: 20ms

memory: 30768kb

input:

99970 100000
2 1
1 3
1 4
1 5
1 6
1 7
8 1
9 1
1 10
11 1
1 12
13 1
1 14
15 1
1 16
17 1
1 18
19 1
1 20
21 1
22 1
23 1
1 24
25 1
1 26
1 27
1 28
29 1
1 30
1 31
1 32
33 1
34 1
35 1
36 1
37 1
38 1
39 1
40 1
41 1
1 42
1 43
1 44
1 45
46 1
47 1
48 1
1 49
50 1
1 51
1 52
1 53
54 1
1 55
56 1
57 1
1 58
59 1
1 60
...

output:

result:

ok q=100000

Test #69:

score: 0

Accepted

time: 16ms

memory: 30624kb

input:

99970 100000
2 1
1 3
1 4
1 5
1 6
7 1
1 8
9 1
1 10
11 1
12 1
13 1
1 14
15 1
1 16
1 17
1 18
19 1
1 20
1 21
1 22
1 23
24 1
25 1
26 1
27 1
28 1
29 1
30 1
1 31
1 32
1 33
34 1
1 35
36 1
37 1
38 1
39 1
1 40
41 1
42 1
1 43
1 44
1 45
46 1
1 47
48 1
49 1
1 50
51 1
52 1
53 1
1 54
55 1
1 56
1 57
1 58
1 59
60 1
...

output:

result:

ok q=100000

Test #70:

score: 0

Accepted

time: 150ms

memory: 28260kb

input:

99970 100000
1 2
3 1
1 4
1 5
1 6
7 1
1 8
9 1
1 10
11 1
1 12
13 1
14 1
15 1
16 1
1 17
18 1
19 1
1 20
1 21
22 1
23 1
1 24
25 1
1 26
1 27
28 1
29 1
30 1
1 31
32 1
1 33
1 34
1 35
36 1
1 37
38 1
39 1
40 1
1 41
42 1
43 1
1 44
45 1
1 46
47 1
48 1
49 1
1 50
51 1
1 52
53 1
1 54
55 1
1 56
57 1
58 1
59 1
60 1
...

output:

result:

ok q=100000

Test #71:

score: 0

Accepted

time: 252ms

memory: 32436kb

input:

99970 100000
2 1
3 1
4 1
1 5
1 6
7 1
8 1
1 9
1 10
11 1
1 12
13 1
14 1
15 1
16 1
17 1
1 18
1 19
20 1
21 1
1 22
23 1
1 24
1 25
26 1
27 1
28 1
29 1
30 1
1 31
1 32
1 33
34 1
1 35
36 1
1 37
38 1
1 39
40 1
1 41
42 1
1 43
1 44
1 45
46 1
47 1
1 48
49 1
50 1
51 1
52 1
1 53
54 1
55 1
56 1
57 1
58 1
59 1
1 60
...

output:

result:

ok q=100000

Test #72:

score: 0

Accepted

time: 13ms

memory: 28048kb

input:

99970 100000
2 1
1 3
5 1
7 1
9 1
1 11
13 1
15 1
1 17
1 19
1 21
1 23
1 25
27 1
1 29
31 1
1 33
1 35
37 1
1 39
1 41
1 43
45 1
47 1
1 49
51 1
1 53
55 1
57 1
59 1
1 61
63 1
65 1
1 67
69 1
71 1
73 1
75 1
77 1
79 1
81 1
1 83
85 1
1 87
1 89
91 1
1 93
1 95
1 97
99 1
1 101
1 103
1 105
107 1
109 1
111 1
1 113
...

output:

result:

ok q=100000

Test #73:

score: 0

Accepted

time: 12ms

memory: 32688kb

input:

99970 100000
2 1
3 1
5 1
7 1
1 9
1 11
1 13
15 1
1 17
19 1
21 1
23 1
1 25
27 1
29 1
1 31
33 1
1 35
37 1
1 39
1 41
1 43
45 1
47 1
1 49
1 51
53 1
1 55
1 57
59 1
61 1
63 1
65 1
67 1
69 1
1 71
73 1
1 75
1 77
79 1
1 81
1 83
85 1
1 87
89 1
91 1
1 93
1 95
97 1
99 1
1 101
103 1
1 105
1 107
1 109
1 111
113 1
...

output:

result:

ok q=100000

Test #74:

score: 0

Accepted

time: 170ms

memory: 29708kb

input:

99970 100000
2 1
3 1
5 1
7 1
9 1
11 1
1 13
1 15
1 17
19 1
1 21
1 23
1 25
1 27
1 29
1 31
1 33
1 35
37 1
39 1
1 41
1 43
1 45
47 1
1 49
51 1
1 53
55 1
57 1
59 1
1 61
63 1
1 65
1 67
1 69
1 71
73 1
75 1
77 1
1 79
1 81
1 83
1 85
1 87
89 1
91 1
93 1
1 95
1 97
1 99
101 1
103 1
1 105
1 107
1 109
111 1
1 113
...

output:

result:

ok q=100000

Test #75:

score: 0

Accepted

time: 313ms

memory: 28116kb

input:

99970 100000
2 1
3 1
5 1
7 1
1 9
11 1
13 1
1 15
1 17
1 19
21 1
1 23
25 1
27 1
1 29
1 31
1 33
1 35
37 1
1 39
41 1
43 1
1 45
1 47
1 49
51 1
53 1
1 55
1 57
59 1
1 61
63 1
65 1
1 67
69 1
1 71
73 1
75 1
77 1
79 1
81 1
83 1
85 1
87 1
89 1
91 1
93 1
95 1
1 97
99 1
101 1
103 1
1 105
1 107
1 109
1 111
113 1
...

output:

result:

ok q=100000

Test #76:

score: -100

Wrong Answer

time: 278ms

memory: 32060kb

input:

99970 100000
1 2
3 1
4 1
1 7
1 10
1 13
16 1
19 1
1 22
25 1
1 28
1 31
34 1
1 37
40 1
1 43
1 46
1 49
52 1
1 55
1 58
61 1
64 1
1 67
70 1
73 1
76 1
1 79
82 1
1 85
88 1
1 91
1 94
97 1
100 1
1 103
106 1
109 1
112 1
115 1
118 1
1 121
124 1
1 127
130 1
1 133
1 136
139 1
1 142
1 145
1 148
1 151
1 154
1 157
1...

output:

result:

wrong answer Chosen edge is not in the cut