QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#374423#6396. Puzzle: KusabiricofxAC ✓34ms41764kbC++174.1kb2024-04-02 14:13:112024-04-02 14:13:11

Judging History

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

  • [2024-04-02 14:13:11]
  • 评测
  • 测评结果:AC
  • 用时:34ms
  • 内存:41764kb
  • [2024-04-02 14:13:11]
  • 提交

answer

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;

#define fi first
#define se second
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
//std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int mod = 998244353;
const int N = 1e5 + 5;
int n, w[N], dep[N];
vector<int> G[N];
vector<pii> ans;
pii dfs(int u) {
    vector<int> d[3];
    for (int v : G[u]) {
        dep[v] = dep[u] + 1;
        auto t = dfs(v);
        if (t.fi != 0) d[t.fi - 1].push_back(t.se); 
    }
    if (w[u]) d[w[u] - 1].push_back(u);
    for (int i = 0; i < 3; i++) sort(d[i].begin(), d[i].end(), [](int x, int y) {
        return dep[x] < dep[y];
    });
    int cnt = 0, lst = 0, lp = 0, idx = 0;
    for (int i = 0; i <= d[0].size(); i++) {
        if ((i == d[0].size()) || (i != 0 && dep[d[0][i]] != dep[d[0][i - 1]])) {
            for (int j = lp; j + 1 < i; j += 2) {
                ans.push_back({d[0][j + 1], d[0][j]});
                //cerr << d[0].size() << ' '<< j << ' ' << d[0][j + 1] << ' ' << d[0][j] << '\n';
            }
            if (lst & 1) idx = d[0][i - 1], ++cnt;
            lst = 0, lp = i;
        }
        ++lst;
    }
    if (abs((int)d[1].size() - (int)d[2].size()) + cnt > 1) {cout << "NO\n" << '\n' ; exit(0);}
    int m = min(d[1].size(), d[2].size());
    if (d[1].size() == d[2].size()) {
        for (int i = 0; i < m; i++) if (dep[d[1][i]] >= dep[d[2][i]]) {cout << "NO\n"; exit(0);}
        for (int i = 0; i < m; i++) ans.push_back({d[1][i], d[2][i]});
    } else if (d[1].size() > d[2].size()) {
        if (m == 0) return {2, d[1][0]};
        vector<int> pre(m, 1), suf(m, 1);
        pre[0] = (dep[d[1][0]] < dep[d[2][0]]);
        for (int i = 1; i < m; i++) pre[i] = (pre[i - 1] && (dep[d[1][i]] < dep[d[2][i]]));
        suf[m - 1] = (dep[d[1].back()] < dep[d[2].back()]);
        for (int i = m - 2; i >= 0; i--) suf[i] = (suf[i + 1] && dep[d[2][i]] > dep[d[1][i + 1]]);
        int pos = -1;
        for (int i = 0; i < d[1].size(); i++) {
            int check = ((i == 0 && suf[0]) || (i + 1 == d[1].size() && pre[m - 1]) ||
            (i > 0 && i + 1 < d[1].size() && pre[i - 1] && suf[i]));
            if (check) {
                pos = i;
                break;
            }
        }
        if (pos == -1) {cout << "NO\n"; exit(0);}
        for (int p = 0, q = 0; p < m; p++, q++) {
            if (q == pos) ++q;
            ans.push_back({d[2][p], d[1][q]});
        }
        return {2, d[1][pos]};
    } else {
        swap(d[1], d[2]);
        if (m == 0) return {3, d[1][0]};
        vector<int> pre(m, 1), suf(m, 1);
        pre[0] = (dep[d[1][0]] > dep[d[2][0]]);
        for (int i = 1; i < m; i++) pre[i] = (pre[i - 1] && (dep[d[1][i]] > dep[d[2][i]]));
        suf[m - 1] = (dep[d[1].back()] > dep[d[2].back()]);
        for (int i = m - 2; i >= 0; i--) suf[i] = (suf[i + 1] && dep[d[2][i]] < dep[d[1][i + 1]]);
        int pos = -1;
        for (int i = 0; i < d[1].size(); i++) {
            int check = ((i == 0 && suf[0]) || (i + 1 == d[1].size() && pre[m - 1]) ||
            (i > 0 && i + 1 < d[1].size() && pre[i - 1] && suf[i]));
            if (check) pos = i;
        }
        if (pos == -1) {cout << "NO\n"; exit(0);}
        for (int p = 0, q = 0; p < m; p++, q++) {
            if (q == pos) ++q;
            ans.push_back({d[2][p], d[1][q]});
        }
        return {3, d[1][pos]};
    }
    return cnt == 1 ? (pii){1, idx} : (pii){0, 0};
}
void MAIN() {
    cin >> n;
    for (int i = 2; i <= n; i++) {
        int u, v;
        static string t;
        cin >> u >> v >> t;
        G[v].push_back(u);
        w[i] = t == "-" ? 0 : t == "Tong" ? 1 : t == "Duan" ? 2 : 3;
    }
    auto t = dfs(1);
    if (t.fi != 0) return cout << "NO\n", void();
    cout << "YES\n";
    for (auto [x, y] : ans) cout << x << ' ' << y << '\n';
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int T = 1;
    //cin >> T;
    while (T--) MAIN();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5996kb

input:

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

output:

YES
5 4
6 8

result:

ok Correct.

Test #2:

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

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
3 10
9 8
2 6
7 5

result:

ok Correct.

Test #3:

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

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

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

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
56115 46666
38802 88119
10006 93143
76473 31531
15988 42604
30148 6569
2008 11412
46703 64525
70618 71289
47748 81204
20514 42353
46131 97634
82155 83516
62410 66867
9975 15712
3205 4978
5622 83026
10902 48783
30893 82167
65878 93809
66951 33377
66936 94549
64411 79128
22475 8453
36857 54702
905...

result:

ok Correct.

Test #5:

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

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
5203 28541
8106 5981
7551 7900
47998 53424
86909 91669
72002 40295
32334 65376
57528 95652
91216 66693
98194 88445
44959 54118
74202 76761
64661 71470
30271 85084
41192 60344
10342 41421
12876 79425
25933 35989
39297 41959
46303 94979
10581 46189
14956 51797
41806 82599
60566 26090
48923 94132
6...

result:

ok Correct.

Test #6:

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

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
19 20
55 65
52 53
46 48
35 36
22 34
58 61
56 57
1097 1206
1522 1593
1890 1938
1217 1365
1191 1295
2158 2188
1764 2845
1646 1408
3147 5721
2746 2810
2937 3194
2710 2399
3657 3778
2668 3580
2259 2179
2122 2174
2204 2379
2392 2449
2218 2499
2233 2369
2020 2077
9174 8244
14498 15184
14362 15193
1040...

result:

ok Correct.

Test #7:

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

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
81 85
107 105
117 103
168 172
273 275
321 333
369 384
314 327
433 463
437 429
543 588
667 639
1167 1273
1160 1375
1117 1176
1021 995
926 929
832 1059
1196 1242
1329 1328
1254 1259
1194 1213
1150 1275
1521 1689
1424 1620
1226 1229
1134 1277
915 1099
1218 1237
1316 1358
1284 1350
2462 2524
2128 23...

result:

ok Correct.

Test #8:

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

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
68 69
118 120
227 237
221 225
266 265
314 323
304 309
343 346
345 352
341 338
347 350
392 401
436 439
469 471
473 474
463 472
480 482
495 499
477 483
567 570
604 613
584 588
576 577
738 744
739 743
730 732
848 851
809 841
881 886
911 930
947 951
1007 1029
964 1002
946 958
914 919
939 942
952 959...

result:

ok Correct.

Test #9:

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

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
238 239
272 274
343 344
415 416
432 433
477 478
512 515
539 544
579 582
631 633
700 711
717 724
719 730
784 787
780 782
773 772
777 783
831 830
824 821
810 816
849 845
858 860
868 872
897 895
876 894
873 871
929 936
986 999
981 984
976 980
964 966
950 955
958 967
968 977
996 997
993 995
1038 103...

result:

ok Correct.

Test #10:

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

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
4915 4986
6570 6738
13597 14195
22019 22308
31792 31800
38225 38186
43803 43898
41995 41864
42327 42725
43807 43871
43542 43953
46361 46356
47608 47755
46932 47521
44955 46885
48486 48399
49839 50116
49668 49912
53355 54823
54273 54714
53853 54239
52524 52947
55640 57456
58053 58348
59228 59658
...

result:

ok Correct.

Test #11:

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

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
34406 34242
23870 14906
79207 28768
68052 50509
32304 70759
36687 70523
68751 36153
3567 47669
70173 18177
58218 50978
56574 27598
6904 46683
47073 79895
4139 85751
17677 83196
90916 65881
67031 44928
25922 49996
95211 28068
69374 43712
19260 84697
70765 32128
79850 30451
12144 92289
51006 99611...

result:

ok Correct.

Test #12:

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

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
66302 15102
40113 37177
67876 67735
98880 70745
84740 75547
71830 88398
85699 62593
6455 71970
21755 94458
39981 74239
13515 71421
71660 37672
91238 90862
19470 42744
72747 13573
81223 10218
87004 15063
4280 19357
6427 44673
68085 92721
33161 17731
358 45357
65914 49326
93622 45470
15964 91832
3...

result:

ok Correct.

Test #13:

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

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
95158 63894
88086 88697
75216 85544
72642 73765
69085 72241
61983 14063
54430 55203
41588 50491
38849 40110
27596 34955
1136 15274
18595 10786
24025 21493
30164 25178
40282 30800
52476 50699
76452 59910
86389 79238
96792 91441
1197 30463
46043 34098
49151 47433
57549 56601
65754 59254
87547 6698...

result:

ok Correct.

Test #14:

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

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
62964 51260
73003 64799
98672 87232
38059 31245
58383 47626
82570 78385
91105 84269
90700 67893
97507 95599
96567 51711
2480 84425
97467 90521
3614 97387
20327 52378
31941 24851
35502 34768
37919 36133
41305 38081
47134 46820
18144 51834
53825 52602
63344 60150
68450 65516
84495 79862
90845 8874...

result:

ok Correct.

Test #15:

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

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
97806 51853
81679 89831
62015 70717
59449 60751
54934 56321
53261 54125
49313 24271
46496 49018
39709 43803
38753 39458
38484 38738
32530 37384
99744 58304
97190 99690
88437 93135
73977 76662
71317 73029
61172 68370
58424 61007
57761 18859
55259 57280
46485 54712
43694 44356
34688 39921
30675 33...

result:

ok Correct.

Test #16:

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

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
336 82705
72014 60220
95022 80211
94029 93125
85950 59250
89854 77242
61755 56243
86382 80147
91748 86818
408 37709
89771 87876
452 83493
481 97158
614 92488
824 95750
31237 30379
31062 31218
30964 31048
30850 30860
30666 30689
30487 30642
30316 31450
30147 30298
29748 29890
29652 29745
29618 29...

result:

ok Correct.

Test #17:

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

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: 21ms
memory: 8452kb

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: 16ms
memory: 8836kb

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: 23ms
memory: 9088kb

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: 22ms
memory: 8896kb

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: 23ms
memory: 8488kb

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: 19ms
memory: 8912kb

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: 13ms
memory: 10968kb

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: 23ms
memory: 7912kb

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: 22ms
memory: 7724kb

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: 18ms
memory: 7552kb

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: 15ms
memory: 7364kb

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: 7616kb

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: 16ms
memory: 7600kb

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: 20ms
memory: 41764kb

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
27101 27102
29449 29450
30581 30582
31108 31109
33544 33545
34348 34349
35394 35395
35626 35627
35741 35742
36325 36326
36979 36980
37025 37026
37780 37781
37916 37917
38565 38566
38778 38779
38882 38884
39162 39163
39440 39441
39609 39610
39688 39689
39923 39924
39994 39995
40980 40981
41017 41...

result:

ok Correct.

Test #32:

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

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
84085 83748
84039 84052
84021 84036
83963 83989
83892 83894
83862 83875
83778 83794
83732 84100
83697 83710
83646 83679
83589 83641
83505 83567
83382 83453
83339 83381
84988 84510
84948 84986
84880 84886
84830 84874
84706 84731
84652 84680
84567 84592
84494 83330
84459 84484
84340 84457
84310 84...

result:

ok Correct.

Test #33:

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

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
9427 44871
75107 58881
7193 33984
9737 33178
31043 89725
50618 31602
870 88133
52086 58845
21758 63567
16605 85296
28152 44633
2705 65095
18041 90927
56227 42717
10288 88253
16710 61450
49645 71661
30561 48970
20860 37354
31734 34821
29953 37862
37189 80450
56610 93257
30431 14996
42455 91146
34...

result:

ok Correct.

Test #34:

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

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
17459 51080
16873 32219
11101 56156
52633 74549
51694 82117
38566 32559
186 48460
25888 41891
83294 84667
52019 87183
77715 88982
13583 78351
83209 87627
62069 46901
8557 86376
986 3604
79770 83765
49864 80461
22996 74127
42259 69795
91303 61472
29187 35154
25303 15829
62442 27245
171 52319
3885...

result:

ok Correct.

Test #35:

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

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
54500 63791
4643 49024
55459 37302
26344 33770
28229 81449
65404 87768
33539 24623
51327 82147
90272 70787
9603 14888
47877 47285
29487 40135
353 4308
34651 72113
41429 58261
22648 64780
81320 68254
50381 57783
25357 85526
43913 76795
41202 34185
46835 41133
140 54622
10796 76020
47575 1923
1383...

result:

ok Correct.

Test #36:

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

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
16406 33409
30277 15284
6139 35906
93724 58902
18729 47922
20659 24670
41216 47533
48839 84590
4161 87728
74471 95897
3459 23810
9591 29076
34342 9185
95194 80103
22109 87229
14850 28966
8235 15423
13261 42356
9379 78438
35400 89672
33413 67130
9648 91476
23306 73800
877 79990
3540 87242
92296 9...

result:

ok Correct.

Test #37:

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

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
5340 14929
7415 15736
22917 23406
15197 14380
14590 24417
7880 3602
15884 1894
12672 9136
3206 5678
15621 24111
20232 14368
25101 21718
1931 7241
19471 24489
8812 23289
12521 22451
130 1629
21864 23008
3189 9095
15113 22734
10604 12465
6641 6996
1537 22852
765 23329
16208 20447
2439 18299
9351 1...

result:

ok Correct.

Test #38:

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

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
20027 82440
37790 82065
13555 55902
9444 93214
14967 54322
8102 47686
23936 71322
77717 78461
45254 48337
52000 83570
24317 29015
723 91719
35283 63413
89556 3250
81387 60951
76768 50544
6264 24023
27168 92751
65278 78391
14547 46265
81407 92070
47136 69857
17204 28099
19861 33721
24774 55462
33...

result:

ok Correct.

Test #39:

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

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
77117 37610
19111 30206
88367 70345
20744 36504
43637 75785
14266 79180
26231 83709
85507 55639
3564 10520
11286 21314
30850 90540
51043 56410
66938 77737
86756 89082
10348 37423
10238 81449
63757 89645
30451 42718
49790 91346
27842 74087
61765 86402
33536 73518
45163 55707
25335 33231
76696 513...

result:

ok Correct.

Test #40:

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

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
91137 22567
6625 32840
2746 72793
58707 49857
6406 9195
17873 75118
13271 70816
35070 36187
34727 36004
60624 77775
40146 56136
3419 7879
81884 50744
75987 35818
56940 90945
1090 12926
73408 77013
45541 48058
55452 26944
55908 58680
43609 78364
45709 77661
32151 55964
12836 71423
21580 52096
122...

result:

ok Correct.

Test #41:

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

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
19363 43838
63190 42715
10322 20329
78903 70798
14986 45972
83054 62809
1456 52182
19710 62218
84523 85461
12256 52940
7475 31914
86366 39273
21575 61296
12897 78432
23096 67416
61831 81263
686 53716
24734 31961
29776 45084
57302 70937
58268 25231
35275 85989
19412 19663
45326 70970
34007 55647
...

result:

ok Correct.

Test #42:

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

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
40096 40387
43478 83783
3661 3917
89303 50150
15374 18917
48940 34799
61144 81225
81589 63107
20682 29948
1795 14730
13591 23638
2983 84669
33792 38473
26822 33668
72727 91365
52159 58495
10991 54079
73581 69625
43086 31305
39523 48339
14352 88518
65295 91546
34909 89085
3467 34637
17285 74155
9...

result:

ok Correct.

Test #43:

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

input:

1

output:

YES

result:

ok Correct.