QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#236171#6396. Puzzle: KusabiPaxton#AC ✓85ms39544kbC++235.9kb2023-11-03 17:32:272023-11-03 17:32:27

Judging History

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

  • [2023-11-03 17:32:27]
  • 评测
  • 测评结果:AC
  • 用时:85ms
  • 内存:39544kb
  • [2023-11-03 17:32:27]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 100;
struct node
{
    int sign, dep, id;
};
vector<int> edge[maxn];
int dep[maxn];
int sign[maxn];
vector<pair<int, int>> ans;

void dfs(int now, int fa)
{
    dep[now] = dep[fa] + 1;
    for (int i = 0; i < edge[now].size(); ++i)
    {
        int id = edge[now][i];
        if (id == fa)
            continue;
        dfs(id, now);
    }
}

node dfs1(int now, int fa)
{
    vector<pair<int, int>> tmp[4]; // 待处理序列 tmp[sign] = {<dep,id>}
    node retu = node{0, 0, 0};     // 当层返回值,id=-1表示无解,0表示没有点
    for (auto a : edge[now])
    {
        if (a == fa)
            continue;
        node rec = dfs1(a, now); // return仅能返回一个点的值
        if (rec.sign == -1)      // 返回-1说明无解
            return node{-1, -1, -1};
        else if (rec.sign > 0)                          // 返回1,2,3说明有返回点
            tmp[rec.sign].push_back({rec.dep, rec.id}); // 加入待处理序列
    }                                                   // 所有儿子节点情况已经添加到tmp中
    if (sign[now] != 0)                                 // 自己拥有标记,加入匹配序列
        tmp[sign[now]].push_back({dep[now], now});
    for (int i = 1; i <= 3; ++i)
        sort(tmp[i].begin(), tmp[i].end(), greater<pair<int, int>>()); // 按照dep降序排序
    if (tmp[3].size())
    {
        int jishu = 1;
        for (int i = 1; i < tmp[3].size(); ++i)
        {
            if (tmp[3][i].first != tmp[3][i - 1].first) // 存在tong无法匹配
            {
                if (jishu % 2) // 奇数个tong
                {
                    if (retu.sign != 0)                                        // 存在待返回值
                        return node{-1, -1, -1};                               // 直接返回无解
                    retu = node{3, tmp[3][i - 1].first, tmp[3][i - 1].second}; // 否则加入返回值
                }
                for (int j = i - jishu; j < i - 1; j += 2)
                    ans.push_back({tmp[3][j].second, tmp[3][j + 1].second});
                jishu = 1;
            }
            else
                jishu++;
        }
        for (int i = tmp[3].size() - jishu; i < tmp[3].size() - 1; i += 2) // 处理最后一段tong
            ans.push_back({tmp[3][i].second, tmp[3][i + 1].second});
        if (jishu % 2) // 奇数个tong,最后一位多余
        {
            if (retu.sign != 0)
                return node{-1, -1, -1};
            retu = node{3, tmp[3][tmp[3].size() - 1].first, tmp[3][tmp[3].size() - 1].second};
        }
    }
    if (tmp[1].size() == tmp[2].size()) // chang,duan长度相同
    {
        for (int i = 0; i < tmp[1].size(); i++)
        {
            if (tmp[1][i].first <= tmp[2][i].first)
                return (node){-1, -1, -1};
            ans.push_back({tmp[1][i].second, tmp[2][i].second});
        }
    }
    else if (tmp[1].size() > tmp[2].size())
    {
        int zz = tmp[1].size() - 1;                  // zz表示chang的指针
        for (int i = tmp[2].size() - 1; i >= 0; i--) // i表示duan的指针
        {
            while (zz >= 0 && tmp[1][zz].first <= tmp[2][i].first) // 若长指针深度小于短指针深度
            {
                if (retu.sign != 0)
                    return node{-1, -1, -1};
                retu = node{1, tmp[1][zz].first, tmp[1][zz].second};
                zz--;
            }
            if (zz >= 0 && tmp[1][zz].first > tmp[2][i].first) // 长指针深度大于短指针深度
            {
                ans.push_back({tmp[1][zz].second, tmp[2][i].second}); // 匹配
                zz--;                                                 // 移位
            }
            else
                return node{-1, -1, -1};
        }
        while (zz >= 0) // 如果duan匹配完了,但是chang还有剩余
        {
            if (retu.sign != 0)
                return node{-1, -1, -1};
            retu = node{1, tmp[1][zz].first, tmp[1][zz].second};
            zz--; // 剩一个且之前没剩
        }
    }
    else if (tmp[1].size() < tmp[2].size()) // 同理
    {
        int zz = 0;
        for (int i = 0; i < tmp[1].size(); i++)
        {
            while (zz < tmp[2].size() && tmp[1][i].first <= tmp[2][zz].first)
            {
                if (retu.sign != 0)
                    return (node){-1, -1, -1};
                retu = (node){2, tmp[2][zz].first, tmp[2][zz].second}, zz++;
            }
            if (zz < tmp[2].size() && tmp[1][i].first > tmp[2][zz].first)
            {
                ans.push_back({tmp[1][i].second, tmp[2][zz].second});
                zz++;
            }
            else
                return node{-1, -1, -1};
        }
        while (zz < tmp[2].size())
        {
            if (retu.sign != 0)
                return node{-1, -1, -1};
            retu = node{2, tmp[2][zz].first, tmp[2][zz].second};
            zz++;
        }
    }
    return retu;
}
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i < n; ++i)
    {
        int a, p, si = 0;
        string t;
        cin >> a >> p >> t;
        if (t == "-")
            si = 0;
        else if (t == "Chang")
            si = 1;
        else if (t == "Duan")
            si = 2;
        else if (t == "Tong")
            si = 3;
        edge[p].push_back(a);
        edge[a].push_back(p);
        sign[a] = si;
    }
    dep[1] = 1;
    dfs(1, 0);
    node finish = dfs1(1, 0);
    if (finish.sign == 0)
    {
        cout << "YES" << endl;
        for (int i = 0; i < ans.size(); i++)
        {
            if (i != ans.size() - 1)
                cout << ans[i].first << " " << ans[i].second << endl;
            else
                cout << ans[i].first << " " << ans[i].second;
        }
    }
    else
        cout << "NO";
    return 0;
}

詳細信息

Test #1:

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

input:

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

output:

YES
5 4
8 6

result:

ok Correct.

Test #2:

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

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

result:

ok Correct.

Test #3:

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

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

score: 0
Accepted
time: 75ms
memory: 10076kb

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

result:

ok Correct.

Test #5:

score: 0
Accepted
time: 52ms
memory: 9952kb

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

result:

ok Correct.

Test #6:

score: 0
Accepted
time: 85ms
memory: 10056kb

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

result:

ok Correct.

Test #7:

score: 0
Accepted
time: 60ms
memory: 10100kb

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

result:

ok Correct.

Test #8:

score: 0
Accepted
time: 66ms
memory: 10272kb

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

result:

ok Correct.

Test #9:

score: 0
Accepted
time: 73ms
memory: 10928kb

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

result:

ok Correct.

Test #10:

score: 0
Accepted
time: 53ms
memory: 11624kb

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

result:

ok Correct.

Test #11:

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

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

result:

ok Correct.

Test #12:

score: 0
Accepted
time: 52ms
memory: 10300kb

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

result:

ok Correct.

Test #13:

score: 0
Accepted
time: 64ms
memory: 10520kb

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

result:

ok Correct.

Test #14:

score: 0
Accepted
time: 47ms
memory: 10732kb

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
98672 87232
73003 64799
62964 51260
91105 84269
82570 78385
58383 47626
38059 31245
97507 95599
90700 67893
96567 51711
84425 2480
97467 90521
97387 3614
99880 90471
77306 65926
99206 90845
88745 84495
79862 68450
65516 63344
60150 53825
52602 52378
51834 47134
46820 41305
38081 37919
36133 3550...

result:

ok Correct.

Test #15:

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

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

result:

ok Correct.

Test #16:

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

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
95022 80211
72014 60220
94029 93125
85950 59250
89854 77242
86382 80147
61755 56243
91748 86818
37709 408
89771 87876
83493 452
97158 481
92488 614
95750 824
99893 99214
98955 98785
98567 98351
98309 97651
97641 97468
97387 97134
97132 96795
96751 96749
96621 96201
96044 94858
94754 94...

result:

ok Correct.

Test #17:

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

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: 50ms
memory: 10240kb

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: 51ms
memory: 9864kb

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: 58ms
memory: 10228kb

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: 55ms
memory: 10296kb

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: 53ms
memory: 10044kb

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: 52ms
memory: 10552kb

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: 49ms
memory: 11720kb

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

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: 52ms
memory: 10352kb

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: 51ms
memory: 10448kb

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: 48ms
memory: 10528kb

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: 47ms
memory: 10636kb

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: 50ms
memory: 10648kb

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: 66ms
memory: 39544kb

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

result:

ok Correct.

Test #32:

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

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
99998 99975
99938 99920
99919 99897
99821 99793
99751 99703
99692 99689
99669 99634
99627 99620
99613 99530
99526 99507
99506 99464
99413 99351
99348 99308
99268 99250
99220 99200
99169 99137
99120 99102
99091 99077
99020 98994
98954 98914
98885 98847
98843 98822
98769 98742
98737 98709
98707 98...

result:

ok Correct.

Test #33:

score: 0
Accepted
time: 55ms
memory: 9736kb

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

result:

ok Correct.

Test #34:

score: 0
Accepted
time: 79ms
memory: 10016kb

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

result:

ok Correct.

Test #35:

score: 0
Accepted
time: 60ms
memory: 9844kb

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

result:

ok Correct.

Test #36:

score: 0
Accepted
time: 83ms
memory: 10036kb

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

result:

ok Correct.

Test #37:

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

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

result:

ok Correct.

Test #38:

score: 0
Accepted
time: 59ms
memory: 9884kb

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

result:

ok Correct.

Test #39:

score: 0
Accepted
time: 61ms
memory: 10076kb

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

result:

ok Correct.

Test #40:

score: 0
Accepted
time: 74ms
memory: 9808kb

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

result:

ok Correct.

Test #41:

score: 0
Accepted
time: 52ms
memory: 9836kb

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

result:

ok Correct.

Test #42:

score: 0
Accepted
time: 67ms
memory: 9792kb

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

result:

ok Correct.

Test #43:

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

input:

1

output:

YES

result:

ok Correct.