QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#186223#6396. Puzzle: KusabiUESTC_Guest_WiFiAC ✓51ms70500kbC++172.9kb2023-09-23 13:47:302023-09-23 13:47:31

Judging History

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

  • [2023-09-23 13:47:31]
  • 评测
  • 测评结果:AC
  • 用时:51ms
  • 内存:70500kb
  • [2023-09-23 13:47:30]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double;
const int N = 2e5 + 50;

using pii = pair<int, int>;
struct cmp {
    bool operator()(const pii &x, const pii &y)const {
        return x.first < y.first;
    };
};
vector<pii> ans;
int n;
int t[N];
vector<int> e[N];
vector<int> depnodes[N];
int dep[N], mx_dep;

multiset<pii, cmp> s[5][N];

void dfs(int u, int fa)
{
    dep[u] = dep[fa] + 1;
    depnodes[dep[u]].push_back(u);
    for (auto v : e[u])
    {
        if (v == fa)
            continue;
        dfs(v, u);
    }
}

void work(int depth)
{
    for (auto u : depnodes[depth])
    {
        for (auto v : e[u])
        {
            if (dep[v] < dep[u])
                continue;
            for (int i = 1; i <= 3; i++)
            {
                for (auto k : s[i][v])
                    s[i][u].insert(k);
                s[i][v].clear();
            }
        }
        if (t[u])
            s[t[u]][u].insert(make_pair(depth, u));
        for (auto it = s[1][u].begin(); it != s[1][u].end() && !s[2][u].empty();)
        {
            auto it2 = s[2][u].lower_bound(*it);
            if (it2 != s[2][u].begin())
            {
                it2--;
                if (it2->first < it->first)
                {
                    ans.emplace_back(it->second, it2->second);
                    it = s[1][u].erase(it);
                    s[2][u].erase(it2);
                }
                else
                    it = next(it);
            }
            else
                it = next(it);
        }
        for (auto it = s[3][u].begin(); it != s[3][u].end() && next(it) != s[3][u].end();)
        {
            if (dep[it->second] == dep[next(it)->second])
            {
                ans.emplace_back(it->second, next(it)->second);
                it = s[3][u].erase(it);
                it = s[3][u].erase(it);
            }
            else
                it = next(it);
        }
        int sum_sz = 0;
        for (int i = 1; i <= 3; i++)
            sum_sz += s[i][u].size();
        if ((sum_sz >= 2) || (u == 1 && sum_sz >= 1))
        {
            cout << "NO\n";
            exit(0);
        }
    }
}

int main()
{
    scanf("%d", &n);
    int cnt_spec = 0;
    for (int i = 1; i < n; i++)
    {
        int ni, pi;
        char ti[10] = {0};
        scanf("%d%d%s", &ni, &pi, ti);
        t[ni] = (ti[0] == 'C' ? 1 : (ti[0] == 'D' ? 2 : (ti[0] == 'T' ? 3 : 0)));
        e[ni].push_back(pi), e[pi].push_back(ni);
        cnt_spec += (ti[0] != '-');
    }
    // if (cnt_spec % 2)
    //     return printf("NO\n"), 0;

    dfs(1, 0);
    mx_dep = *max_element(dep, dep + N);

    for (int d = mx_dep; d >= 1; d--)
        work(d);

    printf("YES\n");
    for (auto [x, y] : ans)
        printf("%d %d\n", x, y);

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 61380kb

input:

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

output:

YES
4 5
8 6

result:

ok Correct.

Test #2:

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

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

result:

ok Correct.

Test #3:

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

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

score: 0
Accepted
time: 51ms
memory: 65408kb

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
77477 68238
92481 55487
90768 80321
61425 26757
85218 93032
79084 61332
81194 38376
96568 84503
87650 80329
90175 80462
91879 56280
80940 85183
92379 45401
51481 47304
48856 37299
68883 55343
86813 15089
65869 61306
55002 20320
69982 68591
74064 85031
73448 61051
45787 29361
42921 55495
95779 82...

result:

ok Correct.

Test #5:

score: 0
Accepted
time: 35ms
memory: 64840kb

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
85007 77529
91387 80143
85287 94990
89837 57819
74899 41068
70086 70043
37273 49983
76734 65251
87688 34335
94573 46653
86640 92239
88248 36497
82691 77530
61348 36957
87863 88167
85912 86273
33907 32074
71093 70825
57414 37315
90566 56018
98528 61875
85275 78637
83397 60916
86820 39881
99054 74...

result:

ok Correct.

Test #6:

score: 0
Accepted
time: 49ms
memory: 65392kb

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
97840 97601
99292 98570
99923 99872
98674 93657
99927 97278
97153 96917
91919 89534
90904 97037
93849 91562
99416 88445
93859 88743
98027 97734
95961 95886
99213 98352
98918 99109
98937 97464
87179 82392
98530 93746
93238 90982
97229 94748
98532 88190
97134 87701
92178 86074
96151 88169
86535 81...

result:

ok Correct.

Test #7:

score: 0
Accepted
time: 45ms
memory: 64760kb

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
92861 91954
93335 91434
93899 98059
97461 92444
95439 94537
94126 92799
89614 87516
97921 93526
92766 88597
98040 87784
94698 88134
96777 95134
99421 91610
87396 89001
86295 85711
89825 93157
97958 92889
90842 83443
84896 84005
91724 85808
95932 98810
99875 89502
87268 87098
91531 86158
96156 95...

result:

ok Correct.

Test #8:

score: 0
Accepted
time: 38ms
memory: 65228kb

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
99449 97710
98482 98203
99472 99169
99187 99881
99926 99695
99372 99486
96571 96519
94569 94328
99882 99179
99495 99924
94920 94118
97800 97267
98388 97034
98506 95628
99032 98256
99734 99105
98060 97831
95502 94210
98303 96199
99149 98563
99392 99312
99511 99191
98548 98119
98644 98661
98925 98...

result:

ok Correct.

Test #9:

score: 0
Accepted
time: 39ms
memory: 65292kb

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
99871 99002
99935 99455
98703 98568
99014 98775
99295 99051
98794 98330
98666 98596
98613 98728
98949 98537
98494 98269
99531 99308
99767 99464
99431 98981
97660 97740
97318 96790
99947 99570
97178 96958
99682 99555
99718 99413
99797 99690
98907 99288
99419 98180
98832 98556
99216 98632
99898 99...

result:

ok Correct.

Test #10:

score: 0
Accepted
time: 31ms
memory: 65340kb

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
99672 98805
98458 98016
98307 98030
97211 96964
99646 98406
99283 96353
97770 96874
95528 95149
95009 95727
95826 95032
93287 92731
93509 92589
94816 94115
92036 91889
99808 91071
98582 91183
93894 93463
95056 90894
88429 88023
93053 90013
91559 89615
91513 90450
88651 87571
88524 87267
89839 87...

result:

ok Correct.

Test #11:

score: 0
Accepted
time: 39ms
memory: 65324kb

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
80198 24098
88171 24783
40562 11139
73062 29042
99142 65243
78891 93050
79869 50504
36153 68751
63196 83117
79302 17788
60234 6386
46536 98139
48385 15034
57729 15842
61505 37679
35563 67516
29431 89988
78374 7572
46167 96843
37345 5629
20243 73598
55234 42327
60615 14379
94930 28006
58735 62595...

result:

ok Correct.

Test #12:

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

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
99253 24514
15102 66302
37177 40113
67735 67876
70745 98880
74239 39981
71421 13515
13573 72747
49326 65914
66307 5659
74307 6751
68801 93527
25142 65868
49908 92842
92302 28268
10387 4763
77194 4231
41886 2882
23941 64953
65085 50595
25338 2766
35889 92736
50684 5973
39951 75236
45778 7638
6566...

result:

ok Correct.

Test #13:

score: 0
Accepted
time: 41ms
memory: 67156kb

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

result:

ok Correct.

Test #14:

score: 0
Accepted
time: 35ms
memory: 65568kb

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
51260 62964
64799 73003
87232 98672
31245 38059
47626 58383
78385 82570
84269 91105
67893 90700
95599 97507
51711 96567
84425 2480
90521 97467
97387 3614
67504 76866
48982 97376
61972 73151
90926 95255
63972 2988
65309 3348
66342 88130
40816 71350
67502 2595
99364 5612
96840 7802
92365 95951
890...

result:

ok Correct.

Test #15:

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

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

result:

ok Correct.

Test #16:

score: 0
Accepted
time: 41ms
memory: 67320kb

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
82705 336
60220 72014
80211 95022
93125 94029
59250 85950
77242 89854
56243 61755
80147 86382
37709 408
86818 91748
87876 89771
83493 452
97158 481
92488 614
95750 824
78516 409
96448 598
86064 2
95747 86859
76526 78815
77425 60638
89238 34692
97446 11713
98648 4966
82710 4358
93523 4090
97896 3...

result:

ok Correct.

Test #17:

score: 0
Accepted
time: 32ms
memory: 65016kb

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: 39ms
memory: 65396kb

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: 26ms
memory: 64764kb

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: 41ms
memory: 65120kb

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: 40ms
memory: 65172kb

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: 42ms
memory: 65084kb

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: 34ms
memory: 65200kb

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: 29ms
memory: 65240kb

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: 28ms
memory: 64836kb

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: 37ms
memory: 65472kb

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: 46ms
memory: 68232kb

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: 37ms
memory: 66604kb

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: 45ms
memory: 68644kb

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: 40ms
memory: 69264kb

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: 33ms
memory: 70500kb

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
100000 99999
99994 99993
99992 99989
99988 99987
99986 99985
99983 99981
99976 99975
99974 99972
99970 99969
99971 99966
99965 99964
99967 99963
99962 99961
99959 99957
99960 99958
99956 99954
99945 99944
99952 99947
99949 99948
99942 99937
99939 99938
99933 99932
99936 99935
99931 99928
99930 9...

result:

ok Correct.

Test #32:

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

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
71956 2
16519 19368
19370 20002
22372 23276
23623 23892
25053 25678
26012 26238
27219 27730
27745 28074
28638 28666
28834 29163
29193 29412
29427 29474
29584 29948
30011 30054
30281 30343
30739 30822
30976 30991
31022 31161
32140 32177
32415 32851
32863 32956
32972 33012
33083 33116
33338 33345
...

result:

ok Correct.

Test #33:

score: 0
Accepted
time: 39ms
memory: 64992kb

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
66636 39643
59669 73972
29538 39373
43825 45676
92094 61662
56374 54079
58779 51777
92038 89214
79715 51729
91931 52001
59992 54089
65054 26175
65249 59652
50472 46097
37619 28787
70144 48367
68486 73300
15616 71114
87207 39620
82288 63988
31389 11598
30372 27837
49740 36554
71700 33598
60608 76...

result:

ok Correct.

Test #34:

score: 0
Accepted
time: 50ms
memory: 65000kb

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
70030 17095
58313 71886
81302 88337
61987 46082
58426 49044
69693 53023
89381 83035
87654 75689
83186 69877
57838 76609
79463 38920
46779 36841
74808 37289
86286 50554
90294 83917
55098 21741
38474 26076
83059 58922
75451 75306
80380 72392
61439 58108
41745 32197
92181 44566
87864 8778
54941 658...

result:

ok Correct.

Test #35:

score: 0
Accepted
time: 48ms
memory: 64964kb

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
90448 71063
70985 47226
54731 53817
71130 60928
60775 52065
92806 53816
78644 61834
66621 34925
91538 76915
72307 61559
77871 61678
78776 56059
50496 61249
52856 62538
54218 50118
46399 88965
39731 56708
71777 57283
68919 25314
74435 43914
73589 40564
75837 70446
53440 29110
81837 64465
72630 92...

result:

ok Correct.

Test #36:

score: 0
Accepted
time: 46ms
memory: 65324kb

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
81930 66577
83933 77584
92455 63072
71866 67573
92912 72371
70317 63337
70245 61159
94399 52559
65297 80055
85114 72465
59449 43588
85452 75636
64850 58621
29443 31276
56643 48922
51157 23195
88704 28814
89798 62845
81017 90058
94855 86719
64539 42364
92183 56961
94394 37510
66889 51463
89546 86...

result:

ok Correct.

Test #37:

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

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
16618 15103
21994 23516
16434 8235
22264 9591
21246 12691
19880 8616
20031 19343
22971 21772
24144 21287
18950 13423
22868 22122
24765 13258
16589 9420
20892 14003
12386 4662
6480 7451
23940 18730
22041 16708
12213 11390
24705 20929
25137 18882
24686 15277
9392 12423
18580 16897
17297 16147
2467...

result:

ok Correct.

Test #38:

score: 0
Accepted
time: 39ms
memory: 64996kb

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
87399 47101
84050 60086
64188 39053
73100 60799
91714 27729
37196 51058
86184 57410
88324 31825
84986 92590
87646 24943
35872 23925
89760 78293
27833 22558
67687 48734
89379 75253
83797 61040
84043 74594
35199 32439
84021 35795
88437 71668
16888 84125
22901 12330
29387 25486
77362 61771
85450 70...

result:

ok Correct.

Test #39:

score: 0
Accepted
time: 45ms
memory: 65248kb

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
64748 50583
99612 83879
55350 47764
84477 44945
60215 65354
51316 51254
59804 54560
73704 64777
89280 79685
76854 82652
61141 34349
67573 62762
80616 30362
80150 51451
63900 34986
91487 88309
99160 78819
66253 55300
70840 50766
70421 26423
60649 32935
86183 60238
97034 86632
46625 43300
24793 30...

result:

ok Correct.

Test #40:

score: 0
Accepted
time: 50ms
memory: 64936kb

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
78204 78156
51967 36397
82427 78133
79070 73958
57455 38876
43404 34717
58713 48285
37948 36514
64018 88498
72670 68802
87893 81149
85556 22228
24511 53774
61304 43245
59479 58325
88072 79174
89317 76311
83169 60999
89571 71803
50155 34101
76502 34710
65296 44985
90010 21100
53737 28817
67079 31...

result:

ok Correct.

Test #41:

score: 0
Accepted
time: 43ms
memory: 65112kb

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
85877 84470
56796 84813
88602 42797
68533 60185
81856 70827
84668 60101
92180 86069
44601 43585
90933 90588
51632 38530
66807 64621
38876 40261
54401 71776
90432 70527
67445 35538
62691 83494
87364 64876
78467 42123
57243 51661
18333 81751
87803 76922
88298 51577
74165 66806
90940 82624
91473 63...

result:

ok Correct.

Test #42:

score: 0
Accepted
time: 41ms
memory: 65068kb

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
84069 61403
92293 84102
88097 64473
81431 55424
72143 51261
86058 79826
92072 52423
63157 47929
82708 67233
91160 89940
76454 57962
57177 51909
60350 59297
85916 62145
66794 35934
50820 36823
86852 55573
69228 68102
66952 44978
75739 39762
87714 86019
88236 32949
64172 49775
49389 33426
50738 52...

result:

ok Correct.

Test #43:

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

input:

1

output:

YES

result:

ok Correct.