QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#528613#6396. Puzzle: Kusabimegumi#AC ✓33ms29724kbC++144.3kb2024-08-23 16:53:502024-08-23 16:53:51

Judging History

This is the latest submission verdict.

  • [2024-08-23 16:53:51]
  • Judged
  • Verdict: AC
  • Time: 33ms
  • Memory: 29724kb
  • [2024-08-23 16:53:50]
  • Submitted

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
inline int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
        f = (c == '-') ? -1 : 1, c = getchar();
    while (c >= '0' && c <= '9')
        x = x * 10 + c - 48, c = getchar();
    return f * x;
}
const int N = 1e5 + 10;
int head[N], cnt;
struct edge {
    int to, next;
} edge[N << 2];
void add(int u, int v) {
    edge[++cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
}
int dep[N], cc[N],
    tt[N]; // 每个点的深度 每个点传上来的数据的深度 传上来的数据对应的点的编号
char a[N];
pair<char, int> P[N];
pair<int, int> ans[N];
int tr, mx;
void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    vector<pair<int, int>> vv[3]; // 分别存子树传上来的长短同
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (v == fa)
            continue;
        dfs(v, u);
        if (!tr)
            return;
        if (a[v] == 'C')
            vv[0].push_back({cc[v], tt[v]});
        else if (a[v] == 'D')
            vv[1].push_back({cc[v], tt[v]});
        else if (a[v] == 'T')
            vv[2].push_back({cc[v], tt[v]});
    }
    if (a[u] == 'C')
        vv[0].push_back({dep[u], u});
    else if (a[u] == 'D')
        vv[1].push_back({dep[u], u});
    else if (a[u] == 'T')
        vv[2].push_back({dep[u], u});
    sort(vv[0].begin(), vv[0].end());
    sort(vv[1].begin(), vv[1].end());
    sort(vv[2].begin(), vv[2].end());
    int len0 = vv[0].size(), len1 = vv[1].size(), len2 = vv[2].size();
    int flag = -1;
    if ((len0 + len1) % 2 + len2 % 2 == 2) {
        tr = 0;
        return;
    }
    if (abs(len0 - len1) >= 2) {
        tr = 0;
        return;
    }
    a[u] = '-';
    for (int i = 0; i < len2; i += 2) {
        if (i == len2 - 1 || vv[2][i].first != vv[2][i + 1].first) {
            if (flag != -1) {
                tr = 0;
                return;
            }
            flag = i, i--;
            continue;
        }
        ans[++mx] = {vv[2][i].second, vv[2][i + 1].second};
    }
    if (len2 % 2 == 0 && flag != -1) {
        tr = 0;
        return;
    } else if (flag != -1) {
        a[u] = 'T';
        cc[u] = vv[2][flag].first;
        tt[u] = vv[2][flag].second;
    }
    if (len0 == len1) {
        for (int i = 0; i < len0; i++) {
            if (vv[0][i].first <= vv[1][i].first) {
                tr = 0;
                return;
            }
            ans[++mx] = {vv[0][i].second, vv[1][i].second};
        }
        return;
    }

    if (len0 > len1) { // 长多
        int r = 0;
        a[u] = 'C';
        int flag = len0 - 1;
        for (int i = 0; i < len1; i++) {
            while (vv[0][r].first <= vv[1][i].first && r < len0) {
                flag = r;
                r++;
                if (r == len0) {
                    tr = 0;
                    return;
                }
            }
            ans[++mx] = {vv[0][r].second, vv[1][i].second};
            r++;
            if (r > len0) {
                tr = 0;
                return;
            }
        }
        cc[u] = vv[0][flag].first;
        tt[u] = vv[0][flag].second;
    }

    else { // 短多
        a[u] = 'D';
        int r = len1 - 1, flag = 0;
        for (int i = len0 - 1; i >= 0; i--) {
            if (r == -1) {
                tr = 0;
                return;
            }
            while (vv[0][i].first <= vv[1][r].first) {
                flag = r;
                r--;
                if (r == -1) {
                    tr = 0;
                    return;
                }
            }
            ans[++mx] = {vv[0][i].second, vv[1][r].second};
            r--;
        }
        cc[u] = vv[1][flag].first;
        tt[u] = vv[1][flag].second;
    }
}
signed main() {
    int n;
    n = read();
    string s;
    tr = 1;
    for (int i = 1; i < n; i++) {
        int u = read(), fa = read();
        cin >> s;
        add(fa, u);
        add(u, fa);
        a[u] = s[0];
    }
    dep[1] = 1;
    dfs(1, 0);
    if (!tr || a[1] != '-')
        cout << "NO\n", exit(0);
    cout << "YES\n";
    for (int i = 1; i <= mx; i++)
        cout << ans[i].first << ' ' << ans[i].second << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7956kb

input:

8
2 1 -
3 1 -
4 2 Tong
5 2 Tong
6 3 Duan
7 3 -
8 7 Chang

output:

YES
8 6
4 5

result:

ok Correct.

Test #2:

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

input:

10
2 1 Duan
3 2 Duan
4 2 -
5 4 Chang
6 2 Chang
7 1 Duan
8 6 Tong
9 6 Tong
10 3 Chang

output:

YES
8 9
10 3
6 2
5 7

result:

ok Correct.

Test #3:

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

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

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

input:

100000
2 1 Duan
3 1 Duan
4 3 -
5 4 Duan
6 3 -
7 4 Duan
8 4 -
9 8 -
10 7 Duan
11 9 -
12 7 Duan
13 7 Duan
14 8 Duan
15 13 -
16 10 Duan
17 11 Duan
18 12 -
19 1 Duan
20 5 Duan
21 4 Duan
22 14 Duan
23 16 -
24 22 Duan
25 16 Duan
26 13 -
27 13 -
28 17 -
29 5 Duan
30 22 -
31 23 -
32 9 Duan
33 5 -
34 30 Duan...

output:

YES
61327 78961
28763 79617
40169 25684
49361 25045
60228 24156
97603 50185
72206 56901
41848 10579
76635 73900
73042 50152
47346 25325
91464 63312
91034 79886
27084 53651
19389 10551
80157 36927
98200 69283
78977 68167
33135 10332
87866 40003
10826 10300
83126 81993
61240 63025
32742 51469
33688 26...

result:

ok Correct.

Test #5:

score: 0
Accepted
time: 11ms
memory: 12472kb

input:

100000
2 1 -
3 2 -
4 3 -
5 4 -
6 4 -
7 6 -
8 7 -
9 5 -
10 9 -
11 10 -
12 6 -
13 12 -
14 11 -
15 9 -
16 14 -
17 16 -
18 10 -
19 15 -
20 13 -
21 20 -
22 17 -
23 22 -
24 22 Duan
25 11 -
26 12 -
27 20 -
28 18 -
29 28 -
30 16 -
31 28 -
32 30 -
33 31 -
34 28 -
35 34 -
36 35 -
37 22 -
38 34 -
39 38 -
40 35...

output:

YES
61365 54260
94528 66883
80746 52379
57632 25539
86270 70587
50931 10692
46315 46038
51215 3973
42355 40468
31649 28057
57657 73329
29098 26291
66814 21998
93763 45470
84353 54966
74078 41071
30942 25774
51936 59287
82007 9388
40293 8527
97856 57690
76507 67337
58992 76115
76631 90319
86905 51620...

result:

ok Correct.

Test #6:

score: 0
Accepted
time: 33ms
memory: 11308kb

input:

100000
2 1 -
3 2 -
4 3 Duan
5 4 Chang
6 5 Duan
7 6 Chang
8 7 Duan
9 8 Chang
10 9 Duan
11 10 Chang
12 11 Duan
13 12 Chang
14 12 Duan
15 14 Chang
16 15 Tong
17 15 Tong
18 17 Duan
19 18 Duan
20 19 Chang
21 18 Duan
22 21 Duan
23 18 Chang
24 21 -
25 24 Duan
26 25 Chang
27 26 Duan
28 27 Chang
29 26 Duan
3...

output:

YES
37 31
42 40
68 64
180 173
196 150
820 771
777 744
809 803
810 799
778 552
556 528
446 374
423 345
920 772
708 570
510 524
652 649
610 588
682 660
433 397
587 396
503 291
686 641
645 549
536 529
478 429
348 321
294 286
323 284
316 282
307 279
376 341
530 501
1160 1152
1757 1446
1685 1435
1413 142...

result:

ok Correct.

Test #7:

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

input:

100000
2 1 -
3 2 -
4 3 -
5 4 -
6 5 -
7 6 -
8 7 -
9 8 -
10 9 Duan
11 10 -
12 11 Chang
13 12 Duan
14 13 Chang
15 14 -
16 15 -
17 16 Duan
18 17 Chang
19 17 -
20 19 -
21 20 -
22 21 -
23 22 -
24 23 -
25 24 -
26 25 Duan
27 26 -
28 27 Duan
29 28 -
30 29 Chang
31 28 -
32 31 Chang
33 32 -
34 32 -
35 34 -
36 ...

output:

YES
131 126
185 174
216 197
189 173
181 163
160 151
144 138
199 169
218 207
255 223
290 287
260 262
359 291
545 489
372 362
468 320
315 306
279 286
247 244
660 603
809 758
902 784
762 708
775 751
779 746
786 663
763 756
716 658
675 589
686 648
591 566
613 582
655 621
711 643
562 579
628 560
690 577
...

result:

ok Correct.

Test #8:

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

input:

100000
2 1 -
3 2 -
4 3 -
5 4 -
6 5 Duan
7 6 -
8 7 -
9 8 -
10 9 Chang
11 10 -
12 11 Duan
13 12 Chang
14 13 -
15 14 Duan
16 15 Chang
17 16 -
18 17 -
19 18 Duan
20 19 -
21 20 -
22 21 -
23 22 Chang
24 23 -
25 24 Duan
26 25 -
27 26 Chang
28 27 -
29 28 -
30 29 -
31 30 Duan
32 31 -
33 32 -
34 33 -
35 34 -
...

output:

YES
161 155
251 249
292 277
424 430
381 368
353 383
386 380
422 429
493 490
532 528
545 526
551 534
540 531
556 555
665 661
642 641
650 639
646 638
624 622
625 621
614 612
630 627
618 615
609 598
706 700
725 718
820 786
875 873
852 835
909 903
865 857
866 850
813 802
810 801
772 770
698 696
780 694
...

result:

ok Correct.

Test #9:

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

input:

100000
2 1 -
3 2 -
4 3 -
5 4 -
6 5 Duan
7 6 -
8 7 -
9 8 Chang
10 9 -
11 10 Duan
12 11 -
13 12 Chang
14 13 Duan
15 14 -
16 15 Chang
17 16 -
18 17 Duan
19 18 -
20 19 Chang
21 20 Duan
22 21 Chang
23 22 -
24 23 Duan
25 24 Chang
26 25 Duan
27 26 -
28 27 -
29 28 Chang
30 29 Duan
31 30 Chang
32 31 -
33 32 ...

output:

YES
308 306
357 356
453 450
556 554
552 549
548 547
570 568
569 567
682 676
672 671
737 738
735 728
805 801
806 794
793 791
910 908
922 914
952 946
1004 991
1016 1011
1024 1014
1164 1156
1160 1153
1155 1151
1147 1140
1102 1097
1094 1095
1093 1089
1076 1075
1123 1122
1129 1125
1135 1134
1154 1157
114...

result:

ok Correct.

Test #10:

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

input:

100000
2 1 -
3 2 -
4 3 -
5 4 -
6 5 -
7 6 -
8 7 -
9 8 -
10 9 -
11 10 -
12 11 -
13 12 -
14 13 -
15 14 -
16 15 -
17 16 -
18 17 -
19 18 -
20 19 -
21 20 -
22 21 -
23 22 -
24 23 -
25 24 -
26 25 -
27 26 -
28 27 -
29 28 -
30 29 -
31 30 -
32 31 -
33 32 -
34 33 -
35 34 -
36 35 -
37 36 -
38 37 -
39 38 -
40 39 ...

output:

YES
4774 4758
12004 11802
12878 12701
14403 14425
15175 15095
16272 16218
15813 15803
16111 15960
17703 17698
18828 18616
20553 20479
22767 22709
25371 24981
24571 23807
23781 23319
28616 28570
27425 26536
29756 29047
30157 29822
29413 29383
35528 35551
34909 34775
34774 33210
33101 33062
39883 3924...

result:

ok Correct.

Test #11:

score: 0
Accepted
time: 16ms
memory: 10700kb

input:

100000
2 1 -
3 1 -
4 2 -
5 1 -
6 1 -
7 2 Duan
8 4 -
9 1 -
10 1 -
11 2 -
12 2 -
13 2 -
14 6 -
15 1 -
16 6 -
17 1 -
18 5 -
19 1 -
20 1 -
21 2 -
22 8 -
23 6 -
24 1 -
25 4 Duan
26 1 -
27 10 -
28 1 -
29 8 -
30 5 -
31 7 -
32 2 -
33 3 -
34 12 -
35 3 -
36 1 -
37 12 -
38 8 -
39 8 -
40 1 -
41 4 -
42 16 -
43 8...

output:

YES
68260 71252
72829 93199
59385 11262
56366 7114
21981 56413
85882 70420
69070 88219
46636 70961
24045 70919
53558 8534
51312 6776
14730 47483
66745 8121
14466 42970
66071 3305
86329 37873
85723 12867
31531 39119
56430 82602
87213 34098
40456 67836
99956 24828
17961 87387
68937 87569
73357 91017
1...

result:

ok Correct.

Test #12:

score: 0
Accepted
time: 12ms
memory: 12644kb

input:

100000
2 1 -
3 1 -
4 1 -
5 1 -
6 1 -
7 1 -
8 1 -
9 1 -
10 3 -
11 1 -
12 2 -
13 2 -
14 2 -
15 1 -
16 2 -
17 2 -
18 1 -
19 1 -
20 1 -
21 2 -
22 1 -
23 2 -
24 2 -
25 1 -
26 1 -
27 4 -
28 1 -
29 2 -
30 3 -
31 1 -
32 10 -
33 6 -
34 4 -
35 1 -
36 2 Duan
37 1 -
38 4 -
39 10 -
40 1 -
41 1 -
42 3 -
43 6 -
44...

output:

YES
67589 89903
25532 2731
39272 68594
15090 81476
60781 71809
45615 98218
9592 13863
38360 41771
32307 67278
46144 98634
70045 36895
90229 56597
21515 87249
7445 44881
99328 70645
70229 51367
44757 15488
38942 68314
31755 361
53849 62803
74966 72268
38644 42791
39590 69049
31128 60607
68719 24390
2...

result:

ok Correct.

Test #13:

score: 0
Accepted
time: 22ms
memory: 11140kb

input:

100000
2 1 Duan
3 1 Duan
4 1 Duan
5 1 Duan
6 1 Duan
7 1 -
8 1 Duan
9 1 Duan
10 1 -
11 1 Duan
12 1 -
13 1 Duan
14 1 Duan
15 1 Duan
16 1 Duan
17 1 Duan
18 2 -
19 1 Duan
20 1 Duan
21 2 -
22 2 Duan
23 1 Duan
24 1 Duan
25 1 Duan
26 1 Duan
27 2 Duan
28 1 Duan
29 2 Duan
30 1 Duan
31 2 Duan
32 1 -
33 1 Duan...

output:

YES
97979 14629
58177 8043
77249 8022
99568 7886
97191 7106
79782 6452
98265 6438
52710 73953
38610 6320
84889 5888
81286 5812
41217 65693
97669 5668
65081 5312
71711 74586
77289 92388
89733 5206
73926 4798
99789 4777
38566 72776
79617 84855
67208 4736
91965 96692
58017 4470
82143 93682
98993 99395
...

result:

ok Correct.

Test #14:

score: 0
Accepted
time: 13ms
memory: 12712kb

input:

100000
2 1 -
3 1 -
4 1 -
5 1 -
6 1 -
7 1 -
8 1 -
9 1 -
10 1 -
11 1 -
12 1 -
13 1 Duan
14 1 -
15 1 -
16 1 -
17 1 -
18 1 -
19 1 -
20 1 -
21 1 -
22 1 -
23 1 -
24 1 -
25 1 -
26 1 -
27 1 -
28 1 -
29 1 Duan
30 1 -
31 1 -
32 2 Duan
33 1 -
34 1 -
35 1 Duan
36 1 -
37 1 -
38 1 -
39 1 -
40 1 -
41 1 -
42 1 -
43...

output:

YES
85599 3382
95392 3013
79392 81526
76883 90600
47562 2266
67095 92236
82645 2087
83119 83294
86680 94655
53700 98104
59880 1891
84824 94429
38939 1867
72196 86276
74866 1851
73841 1832
33013 52187
75982 82555
60149 84502
77895 89910
90018 94488
52964 1798
62543 1780
45755 50707
63884 96747
67922 ...

result:

ok Correct.

Test #15:

score: 0
Accepted
time: 12ms
memory: 10612kb

input:

100000
2 1 Duan
3 1 -
4 1 -
5 1 Duan
6 1 -
7 1 -
8 1 -
9 1 -
10 1 -
11 1 -
12 1 -
13 1 -
14 1 -
15 1 -
16 1 -
17 1 -
18 1 -
19 1 -
20 1 -
21 1 -
22 1 -
23 1 -
24 1 -
25 1 -
26 1 -
27 1 -
28 1 -
29 1 -
30 1 -
31 1 -
32 1 -
33 1 Duan
34 1 -
35 1 -
36 1 -
37 1 -
38 1 -
39 1 -
40 1 -
41 1 -
42 1 -
43 1 ...

output:

YES
93600 1484
65492 1226
54647 80577
87425 98136
92548 1057
90647 95875
88522 91502
65449 864
63757 78454
57780 863
79380 91133
90975 859
77801 81087
69230 93397
63165 847
88299 841
61658 83594
91139 96200
67080 81529
96324 96779
74882 99215
99183 99293
56495 87893
78381 778
44807 81594
82056 767
8...

result:

ok Correct.

Test #16:

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

input:

100000
2 1 Duan
3 1 Duan
4 1 -
5 1 Duan
6 1 -
7 1 Duan
8 1 Duan
9 1 Duan
10 1 Duan
11 1 -
12 1 -
13 1 -
14 1 Duan
15 1 Duan
16 1 Duan
17 1 -
18 1 Duan
19 1 Duan
20 1 Duan
21 1 -
22 1 -
23 1 Duan
24 1 Duan
25 1 Duan
26 1 -
27 1 -
28 1 Duan
29 1 Duan
30 1 -
31 1 Duan
32 1 Duan
33 1 -
34 1 Duan
35 1 -
...

output:

YES
83464 705
95111 622
99954 575
91152 92518
93861 99688
92449 531
71582 528
66385 524
91774 518
95679 96388
95051 502
68161 495
92051 491
71560 79514
91617 486
92920 466
91709 456
69375 71375
82066 86414
94412 455
89074 451
86461 92101
97252 99900
86105 437
78526 436
65746 90094
82699 93000
84619 ...

result:

ok Correct.

Test #17:

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

input:

100000
2 1 -
3 1 -
4 2 -
5 2 -
6 2 Duan
7 3 -
8 1 -
9 1 -
10 6 -
11 3 -
12 2 -
13 7 -
14 1 -
15 9 -
16 11 -
17 13 -
18 9 -
19 16 -
20 19 -
21 8 -
22 5 -
23 14 -
24 21 -
25 21 -
26 16 -
27 5 -
28 5 -
29 19 -
30 8 -
31 24 -
32 30 -
33 12 Duan
34 9 -
35 12 Duan
36 6 -
37 15 -
38 26 -
39 29 -
40 13 -
41...

output:

NO

result:

ok Correct.

Test #18:

score: 0
Accepted
time: 12ms
memory: 12608kb

input:

100000
2 1 Duan
3 2 Duan
4 3 -
5 3 Duan
6 4 -
7 4 Duan
8 3 Duan
9 2 -
10 4 Duan
11 8 Duan
12 6 -
13 3 Duan
14 6 Duan
15 7 Duan
16 6 Duan
17 14 Tong
18 7 -
19 16 Duan
20 14 Duan
21 12 Duan
22 20 Duan
23 14 Duan
24 19 -
25 2 Duan
26 22 -
27 24 Duan
28 8 Duan
29 4 Duan
30 23 Duan
31 24 Duan
32 23 Duan
...

output:

NO

result:

ok Correct.

Test #19:

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

input:

100000
2 1 -
3 2 -
4 3 -
5 4 -
6 5 -
7 4 -
8 7 -
9 8 -
10 9 -
11 10 Duan
12 9 -
13 12 -
14 12 -
15 10 -
16 8 -
17 13 -
18 10 -
19 14 -
20 13 -
21 19 -
22 19 Duan
23 11 -
24 23 Duan
25 23 -
26 5 -
27 22 -
28 22 Duan
29 17 -
30 29 -
31 29 -
32 17 -
33 27 -
34 33 Duan
35 31 -
36 24 -
37 34 -
38 37 -
39...

output:

NO

result:

ok Correct.

Test #20:

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

input:

100000
2 1 Duan
3 2 Chang
4 3 -
5 4 -
6 5 -
7 6 Duan
8 7 -
9 8 Chang
10 9 Duan
11 10 Chang
12 11 -
13 12 Duan
14 13 Chang
15 13 -
16 15 -
17 15 -
18 15 Duan
19 18 -
20 19 Duan
21 19 Chang
22 20 -
23 22 -
24 21 Duan
25 23 -
26 22 -
27 25 Chang
28 26 -
29 28 Duan
30 24 Chang
31 28 -
32 23 -
33 28 -
34...

output:

NO

result:

ok Correct.

Test #21:

score: 0
Accepted
time: 18ms
memory: 12984kb

input:

100000
2 1 Duan
3 2 Chang
4 3 -
5 4 -
6 5 Duan
7 6 -
8 7 -
9 8 Chang
10 9 Duan
11 10 Chang
12 11 Duan
13 12 Chang
14 12 -
15 14 -
16 15 Duan
17 16 Chang
18 17 -
19 17 Duan
20 19 -
21 19 Chang
22 21 -
23 21 Duan
24 23 Duan
25 24 Chang
26 24 Chang
27 24 Duan
28 27 -
29 28 Chang
30 28 Duan
31 30 -
32 3...

output:

NO

result:

ok Correct.

Test #22:

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

input:

100000
2 1 Duan
3 2 Chang
4 3 Duan
5 4 -
6 5 Chang
7 6 -
8 7 Duan
9 8 -
10 9 Chang
11 10 Duan
12 11 Chang
13 12 -
14 13 Duan
15 14 -
16 15 Chang
17 16 -
18 17 Duan
19 18 -
20 19 -
21 20 -
22 21 Chang
23 22 -
24 23 Duan
25 24 Chang
26 25 -
27 26 Duan
28 27 -
29 28 Chang
30 28 Duan
31 30 -
32 31 Chang...

output:

NO

result:

ok Correct.

Test #23:

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

input:

100000
2 1 Duan
3 2 -
4 3 -
5 4 -
6 5 -
7 6 -
8 7 -
9 8 -
10 9 -
11 10 -
12 11 Chang
13 12 Duan
14 13 -
15 14 -
16 15 Chang
17 16 Duan
18 17 Chang
19 18 -
20 19 -
21 20 -
22 21 -
23 22 -
24 23 -
25 24 -
26 25 Duan
27 26 -
28 27 -
29 28 -
30 29 -
31 30 -
32 31 -
33 32 -
34 33 Chang
35 34 -
36 35 -
37...

output:

NO

result:

ok Correct.

Test #24:

score: 0
Accepted
time: 14ms
memory: 11404kb

input:

100000
2 1 -
3 2 -
4 3 -
5 4 -
6 5 Duan
7 6 -
8 7 Chang
9 8 -
10 9 -
11 10 -
12 11 -
13 12 -
14 13 Duan
15 14 -
16 15 Chang
17 16 -
18 17 -
19 18 -
20 19 Duan
21 20 -
22 21 -
23 22 -
24 23 Chang
25 24 -
26 25 Duan
27 26 Chang
28 27 Duan
29 28 -
30 29 -
31 30 -
32 31 Chang
33 32 Duan
34 33 -
35 34 -
...

output:

NO

result:

ok Correct.

Test #25:

score: 0
Accepted
time: 11ms
memory: 12632kb

input:

100000
2 1 Duan
3 1 -
4 1 -
5 1 -
6 3 -
7 2 -
8 2 -
9 4 -
10 1 -
11 2 -
12 3 Duan
13 2 -
14 4 -
15 3 -
16 3 -
17 2 -
18 2 -
19 1 -
20 7 Duan
21 1 -
22 15 -
23 6 -
24 1 -
25 8 -
26 11 -
27 5 -
28 16 -
29 17 -
30 16 -
31 3 -
32 7 -
33 3 Duan
34 7 Duan
35 3 -
36 8 -
37 6 -
38 16 -
39 3 -
40 3 -
41 11 -...

output:

NO

result:

ok Correct.

Test #26:

score: 0
Accepted
time: 14ms
memory: 12964kb

input:

100000
2 1 -
3 1 -
4 1 -
5 1 -
6 1 -
7 1 Duan
8 1 -
9 1 -
10 1 -
11 3 -
12 2 -
13 1 -
14 1 -
15 1 -
16 2 -
17 1 Duan
18 3 -
19 1 -
20 1 Duan
21 8 -
22 2 -
23 3 -
24 3 Duan
25 1 -
26 1 -
27 1 -
28 1 -
29 4 -
30 1 -
31 3 -
32 3 -
33 3 -
34 2 -
35 1 -
36 1 Duan
37 1 -
38 3 -
39 2 -
40 4 -
41 2 Duan
42 ...

output:

NO

result:

ok Correct.

Test #27:

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

input:

100000
2 1 Duan
3 1 Duan
4 1 Duan
5 1 Duan
6 1 Duan
7 1 Duan
8 1 Duan
9 1 Duan
10 1 Duan
11 1 Duan
12 1 Duan
13 1 Duan
14 2 Duan
15 1 Duan
16 1 Duan
17 1 Duan
18 2 Duan
19 1 Duan
20 1 -
21 1 Duan
22 1 Duan
23 1 Duan
24 1 Duan
25 1 Duan
26 1 Duan
27 2 Duan
28 1 Duan
29 1 Duan
30 1 -
31 1 Duan
32 1 Du...

output:

NO

result:

ok Correct.

Test #28:

score: 0
Accepted
time: 18ms
memory: 11040kb

input:

100000
2 1 -
3 1 Duan
4 1 -
5 1 -
6 1 -
7 1 Duan
8 1 -
9 1 Duan
10 1 -
11 1 Duan
12 1 Duan
13 1 Duan
14 1 Duan
15 1 Duan
16 1 -
17 1 Duan
18 1 Duan
19 1 Duan
20 1 Duan
21 1 -
22 1 -
23 1 Duan
24 1 -
25 1 Duan
26 1 Duan
27 1 Duan
28 1 Duan
29 1 Duan
30 1 Duan
31 1 Duan
32 1 -
33 1 -
34 1 Duan
35 1 Du...

output:

NO

result:

ok Correct.

Test #29:

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

input:

100000
2 1 Duan
3 1 Duan
4 1 Duan
5 1 Duan
6 1 Duan
7 1 Duan
8 1 -
9 1 Duan
10 1 Duan
11 1 Duan
12 1 -
13 1 Duan
14 1 Duan
15 1 Duan
16 1 Duan
17 1 Duan
18 1 Duan
19 1 Duan
20 1 -
21 1 -
22 1 Duan
23 1 -
24 1 Duan
25 1 Duan
26 1 Duan
27 1 Duan
28 1 Duan
29 1 Duan
30 1 Duan
31 1 Duan
32 1 Duan
33 1 -...

output:

NO

result:

ok Correct.

Test #30:

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

input:

100000
2 1 Duan
3 1 -
4 1 Duan
5 1 Duan
6 1 Duan
7 1 Duan
8 1 Duan
9 1 Duan
10 1 Duan
11 1 Duan
12 1 Duan
13 1 Duan
14 1 Duan
15 1 Duan
16 1 Duan
17 1 Duan
18 1 Duan
19 1 -
20 1 Duan
21 1 Duan
22 1 Duan
23 1 Duan
24 1 Duan
25 1 Duan
26 1 Duan
27 1 Duan
28 1 -
29 1 Duan
30 1 Duan
31 1 Duan
32 1 -
33 ...

output:

NO

result:

ok Correct.

Test #31:

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

input:

100000
2 1 Duan
3 2 -
4 3 Chang
5 4 -
6 5 Duan
7 6 Chang
8 7 -
9 8 -
10 9 Duan
11 10 Chang
12 11 Duan
13 12 Chang
14 13 Duan
15 14 Chang
16 15 -
17 16 -
18 17 -
19 18 Duan
20 19 -
21 20 -
22 21 Chang
23 22 Duan
24 23 Chang
25 24 -
26 25 Duan
27 26 Chang
28 27 Duan
29 28 -
30 29 Chang
31 30 Duan
32 3...

output:

YES
38669 38668
43574 43573
44576 44575
44897 44896
47955 47954
48087 48086
51732 51731
52699 52698
53053 53051
53844 53843
54080 54079
55170 55169
56248 56247
56591 56590
57029 57028
57090 57089
57209 57208
57206 57205
57692 57691
57809 57806
58262 58261
58319 58318
59077 59076
59131 59130
59428 59...

result:

ok Correct.

Test #32:

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

input:

100000
2 1 Duan
3 1 -
4 1 -
5 1 -
6 1 -
7 1 -
8 1 -
9 1 -
10 1 -
11 1 -
12 1 Tong
13 1 -
14 1 -
15 1 -
16 1 Tong
17 1 -
18 1 -
19 1 -
20 1 -
21 1 -
22 1 Tong
23 1 -
24 1 -
25 1 -
26 1 -
27 1 -
28 1 -
29 1 -
30 1 -
31 1 -
32 1 -
33 1 -
34 1 -
35 1 -
36 1 -
37 1 -
38 1 Tong
39 1 -
40 1 -
41 1 -
42 1 -...

output:

YES
90226 92627
80552 98157
66335 67953
85511 86134
86460 86996
89512 89806
92271 94233
96463 99736
48609 55714
56615 60624
64372 65770
69427 71357
72862 73888
73891 74512
77025 79593
80845 81710
81856 82075
82419 83893
85318 85374
85698 87691
88314 89327
89757 91747
92085 92584
93512 95440
97391 99...

result:

ok Correct.

Test #33:

score: 0
Accepted
time: 16ms
memory: 12724kb

input:

93284
2 1 -
3 1 Duan
4 2 -
5 4 -
6 2 -
7 4 Duan
8 1 -
9 4 -
10 4 Duan
11 6 -
12 7 -
13 6 -
14 1 Duan
15 4 -
16 9 -
17 12 -
18 15 -
19 6 Duan
20 1 -
21 15 -
22 2 -
23 5 Duan
24 7 -
25 22 -
26 13 -
27 12 -
28 6 -
29 27 Duan
30 7 Duan
31 9 -
32 14 -
33 3 -
34 21 -
35 18 -
36 35 -
37 7 -
38 17 Duan
39 2...

output:

YES
74513 20816
81879 66130
89777 35338
62475 73761
71335 37702
33453 23517
56223 15222
86688 91225
29499 7805
58463 86109
24560 41026
47941 5910
44357 15686
70706 20522
22815 9149
46379 66681
81135 71082
47858 24083
85674 46291
79873 75184
73465 87023
33095 41087
9719 56514
53207 3487
82993 58715
7...

result:

ok Correct.

Test #34:

score: 0
Accepted
time: 28ms
memory: 13168kb

input:

92284
2 1 Duan
3 2 -
4 3 Duan
5 2 Duan
6 3 -
7 4 Duan
8 6 Duan
9 4 Duan
10 6 Duan
11 4 Duan
12 8 Chang
13 1 Duan
14 5 Duan
15 5 -
16 15 Duan
17 15 Duan
18 13 Chang
19 12 Duan
20 4 -
21 1 Duan
22 17 Duan
23 2 Duan
24 14 Duan
25 17 Duan
26 22 Duan
27 4 -
28 26 Duan
29 9 Duan
30 15 Duan
31 3 Duan
32 7 ...

output:

YES
72399 59373
64277 59795
76031 62511
62495 48883
59778 39444
86492 16425
13682 49780
65245 46706
57764 46022
12089 12085
91021 12688
41203 66749
40403 17794
90300 62095
62751 58704
19440 22903
35611 40542
77274 71273
72403 27633
47603 27548
44456 44368
16807 41743
24344 12412
61518 41680
52077 61...

result:

ok Correct.

Test #35:

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

input:

93444
2 1 -
3 1 Duan
4 1 Duan
5 2 -
6 4 -
7 3 -
8 6 Duan
9 6 Duan
10 9 -
11 2 -
12 1 -
13 11 -
14 5 -
15 14 Duan
16 11 -
17 16 -
18 4 -
19 7 Duan
20 15 -
21 17 -
22 21 -
23 20 -
24 23 Duan
25 7 -
26 14 Duan
27 18 -
28 13 Duan
29 2 Duan
30 19 Duan
31 5 -
32 7 Duan
33 23 Duan
34 17 Duan
35 2 Duan
36 2...

output:

YES
36095 18291
42330 58464
65585 59400
28016 1955
74817 40901
53918 89642
4623 63353
84984 82334
61350 57215
68628 54608
89498 6183
51738 50593
59238 36029
76817 62682
78448 8962
53894 77371
25512 32196
36051 72379
61507 15907
45334 17172
24983 14874
57517 79759
7489 4252
58719 61241
40373 47115
20...

result:

ok Correct.

Test #36:

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

input:

98244
2 1 Duan
3 1 Duan
4 3 Duan
5 4 Duan
6 4 Duan
7 4 Duan
8 5 Duan
9 8 Duan
10 5 Duan
11 9 Duan
12 3 Duan
13 11 Tong
14 5 Duan
15 5 Duan
16 12 Duan
17 2 Duan
18 3 Duan
19 4 Duan
20 2 Duan
21 6 Duan
22 21 Duan
23 1 -
24 15 -
25 20 Duan
26 8 Duan
27 13 Duan
28 12 Duan
29 22 Duan
30 24 Duan
31 21 Dua...

output:

YES
38963 31567
95866 13251
95270 63302
92175 54023
59312 48934
93485 24639
26380 21809
59491 39929
74962 50304
93197 37132
32873 50798
89682 3734
10918 68142
77790 61493
13569 2062
44405 89860
13525 3203
69831 52369
49035 43739
38807 28930
75766 66372
39400 86527
15465 3875
26746 27472
26723 1690
1...

result:

ok Correct.

Test #37:

score: 0
Accepted
time: 4ms
memory: 10044kb

input:

25284
2 1 Duan
3 2 -
4 3 -
5 3 Duan
6 2 Duan
7 3 Duan
8 1 Duan
9 5 -
10 4 -
11 5 Duan
12 4 Duan
13 1 Duan
14 4 -
15 10 Duan
16 8 -
17 13 -
18 15 -
19 12 -
20 16 Duan
21 6 Duan
22 2 Duan
23 19 -
24 12 -
25 2 -
26 19 Duan
27 5 -
28 4 -
29 9 -
30 12 Duan
31 7 Duan
32 31 -
33 21 -
34 24 Duan
35 28 Duan
...

output:

YES
14626 21135
14096 13835
23638 4428
14105 14395
14359 8988
12572 18822
20771 1866
23534 15210
24821 7235
16843 1084
22081 18384
23584 9125
17968 7918
16796 24718
23519 8913
23223 3762
17039 1868
15456 7940
6852 2957
16581 14498
19923 9470
9699 1916
16119 17156
6193 1797
8613 13962
3543 18684
845 ...

result:

ok Correct.

Test #38:

score: 0
Accepted
time: 29ms
memory: 11056kb

input:

93246
2 1 Duan
3 2 Duan
4 3 Duan
5 1 -
6 4 Tong
7 4 Duan
8 4 Duan
9 8 -
10 6 Duan
11 2 Duan
12 1 Duan
13 11 Duan
14 8 Duan
15 1 Duan
16 8 Duan
17 10 Duan
18 3 Duan
19 1 Duan
20 18 Duan
21 10 Duan
22 14 Duan
23 11 Duan
24 19 Duan
25 21 Duan
26 17 Duan
27 24 Duan
28 24 Duan
29 17 Tong
30 23 Duan
31 17...

output:

YES
89030 81889
92091 44827
92357 18804
88411 71114
41235 19189
37071 26335
34183 92987
88624 13889
7117 5382
63386 9021
70522 26290
74182 44641
63647 36015
91664 90356
62270 48141
68439 32796
71774 29179
86091 76068
62275 27623
92998 19705
89771 11009
8510 4652
64403 3815
9990 40253
62617 1699
8489...

result:

ok Correct.

Test #39:

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

input:

99837
2 1 -
3 1 -
4 3 Duan
5 2 Duan
6 5 Duan
7 3 Duan
8 5 -
9 6 Duan
10 4 -
11 4 -
12 6 Duan
13 8 -
14 7 -
15 10 Duan
16 11 Duan
17 8 Duan
18 6 -
19 13 Duan
20 16 Duan
21 20 -
22 19 Chang
23 4 Duan
24 13 Duan
25 21 -
26 17 Duan
27 7 Duan
28 8 -
29 3 -
30 18 -
31 21 Duan
32 27 Duan
33 21 Duan
34 17 -...

output:

YES
92676 10410
64479 39274
94138 78859
30205 21274
30056 8785
37886 83693
88306 73635
28522 11691
57401 30919
64681 38138
9496 93491
63118 51332
66215 28452
92328 51297
94426 23727
77931 74562
34253 42129
48303 23327
51081 79346
74255 10299
78121 69759
64700 16245
84360 90972
62165 95214
17883 1087...

result:

ok Correct.

Test #40:

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

input:

91248
2 1 Duan
3 1 Duan
4 1 Duan
5 2 Duan
6 3 Duan
7 3 Chang
8 2 Duan
9 1 Duan
10 7 Duan
11 10 Duan
12 4 Duan
13 2 Duan
14 11 Duan
15 6 Duan
16 8 Duan
17 7 Duan
18 2 Duan
19 15 Duan
20 4 Duan
21 7 Duan
22 6 Duan
23 6 Duan
24 20 Duan
25 13 Duan
26 22 Duan
27 5 Duan
28 19 Duan
29 14 Duan
30 12 -
31 8 ...

output:

YES
88200 84342
84352 76377
63352 45791
88470 50883
44680 18535
31347 47797
50617 12022
66762 6719
67174 5130
89212 77457
66802 59725
69332 46630
90420 56151
48424 44293
74573 50828
46329 68733
19496 53256
32591 15888
80259 6154
25680 27747
81109 25066
32892 5287
10884 54094
89180 31562
2675 2581
87...

result:

ok Correct.

Test #41:

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

input:

93538
2 1 -
3 2 -
4 2 -
5 3 Duan
6 4 -
7 4 -
8 2 -
9 1 -
10 7 -
11 4 Duan
12 8 -
13 9 -
14 1 Duan
15 7 Duan
16 3 -
17 5 -
18 14 Duan
19 5 -
20 7 -
21 15 Duan
22 9 -
23 8 -
24 16 Duan
25 5 Duan
26 6 Duan
27 10 -
28 7 -
29 21 Duan
30 1 -
31 18 -
32 13 -
33 6 -
34 28 -
35 16 Duan
36 32 Duan
37 22 -
38 ...

output:

YES
71885 78212
37718 6100
49527 40991
92012 80389
81271 68659
54473 43095
79642 41814
57857 73661
48483 24540
52557 16398
41232 56423
62371 3709
48165 78939
74690 74318
68804 61871
24274 24101
70628 64890
84790 41770
53698 40451
39635 42520
91102 25034
90535 39256
77572 90078
91112 11894
72404 1639...

result:

ok Correct.

Test #42:

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

input:

92384
2 1 Duan
3 2 -
4 3 Duan
5 3 Duan
6 3 -
7 2 Duan
8 1 -
9 7 Duan
10 5 Chang
11 4 -
12 3 Duan
13 7 -
14 9 Duan
15 14 Chang
16 3 Duan
17 6 Duan
18 10 Duan
19 17 Duan
20 10 -
21 2 Duan
22 10 -
23 5 Duan
24 18 -
25 11 -
26 13 Duan
27 12 Duan
28 1 -
29 18 Duan
30 28 Duan
31 28 -
32 16 -
33 27 Duan
34...

output:

YES
65469 52483
66814 39644
44726 11062
79880 9868
59560 37247
88171 77144
76272 24217
61782 85792
80279 57105
68289 37735
58829 31363
44877 26773
91292 18959
57214 43740
15239 7777
90532 9911
7970 31792
48350 12673
70419 63278
78633 33091
87915 72507
71152 37461
55042 52979
72909 64528
44823 41920
...

result:

ok Correct.

Test #43:

score: 0
Accepted
time: 0ms
memory: 5900kb

input:

1

output:

YES

result:

ok Correct.