QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#103930#6396. Puzzle: Kusabihos_lyricAC ✓49ms10460kbC++143.8kb2023-05-07 21:07:222023-05-07 21:07:23

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-07 21:07:23]
  • 评测
  • 测评结果:AC
  • 用时:49ms
  • 内存:10460kb
  • [2023-05-07 21:07:22]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


int N;
vector<int> P;
vector<char> T;

bool solve() {
  vector<int> dep(N, 0);
  for (int u = 1; u < N; ++u) {
    dep[u] = dep[P[u]] + 1;
  }
  vector<vector<int>> dp(N);
  for (int u = 0; u < N; ++u) if (T[u] != '-') {
    dp[u].push_back(u);
  }
  vector<pair<int, int>> ans;
  for (int u = N; --u >= 0; ) {
    vector<pair<int, int>> cs, ds, ts;
    for (const int v : dp[u]) {
      ((T[v] == 'C') ? cs : (T[v] == 'D') ? ds : ts).emplace_back(dep[v], v);
    }
    sort(cs.begin(), cs.end());
    sort(ds.begin(), ds.end());
    sort(ts.begin(), ts.end());
// cerr<<u<<": "<<cs<<" "<<ds<<" "<<ts<<endl;
    const int csLen = cs.size();
    const int dsLen = ds.size();
    const int tsLen = ts.size();
    vector<int> remain;
    if (csLen <= dsLen) {
      // keep smallest in ds
      reverse(cs.begin(), cs.end());
      reverse(ds.begin(), ds.end());
      vector<int> used(dsLen, 0);
      for (int i = 0, j = 0; i < csLen; ++i) {
        for (; j < dsLen && !(cs[i].first > ds[j].first); ++j) {}
        if (j == dsLen) return false;
        used[j] = 1;
        ans.emplace_back(cs[i].second, ds[j].second);
        ++j;
      }
      for (int j = 0; j < dsLen; ++j) if (!used[j]) {
        remain.push_back(ds[j].second);
      }
    } else {
      // keep largest in cs
      vector<int> used(csLen, 0);
      for (int i = 0, j = 0; j < dsLen; ++j) {
        for (; i < csLen && !(cs[i].first > ds[j].first); ++i) {}
        if (i == csLen) return false;
        used[i] = 1;
        ans.emplace_back(cs[i].second, ds[j].second);
        ++i;
      }
      for (int i = 0; i < csLen; ++i) if (!used[i]) {
        remain.push_back(cs[i].second);
      }
    }
    for (int i = 0; i < tsLen; ) {
      if (i + 1 < tsLen && ts[i].first == ts[i + 1].first) {
        ans.emplace_back(ts[i].second, ts[i + 1].second);
        i += 2;
      } else {
        remain.push_back(ts[i].second);
        i += 1;
      }
    }
    if (remain.size() >= 2) {
      return false;
    }
    for (const int v : remain) {
      if (!~P[u]) {
        return false;
      }
      dp[P[u]].push_back(v);
    }
  }
  
  puts("YES");
  for (const auto &e : ans) {
    printf("%d %d\n", e.first + 1, e.second + 1);
  }
  return true;
}

int main() {
  char buf[110];
  
  for (; ~scanf("%d", &N); ) {
    P.assign(N, -1);
    T.assign(N, '-');
    for (int u = 1; u < N; ++u) {
      scanf("%*d%d%s", &P[u], buf);
      --P[u];
      T[u] = buf[0];
    }
    
    const bool res = solve();
    if (!res) {
      puts("NO");
    }
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1ms
memory: 3584kb

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: 2ms
memory: 3508kb

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

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

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
99893 99188
98950 98791
99758 98563
98540 98299
99817 98287
99347 98253
98789 98179
99611 98000
98580 97798
98524 97712
99795 97659
98151 97544
98357 97488
99308 97469
98460 97428
99596 97313
97733 97130
99609 97014
99598 96874
98948 96860
99468 96780
97621 96654
97426 96616
99500 96541
97481 96...

result:

ok Correct.

Test #5:

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

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
98903 98544
97809 99744
96073 95253
95666 95222
96756 95187
98686 94042
95407 94000
99938 93557
97078 92888
97706 92767
93318 92253
99751 91867
95022 89309
97379 87280
86868 86612
99527 86322
88203 85608
96472 98912
89195 84953
87174 84533
98944 84189
94789 84015
88017 83849
99600 83839
84725 87...

result:

ok Correct.

Test #6:

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

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
99952 99901
99923 99872
99865 99855
99820 99819
99842 99761
99947 99711
99869 99675
99767 99660
99726 99649
99673 99613
99870 99603
99625 99563
99882 99529
99662 99525
99719 99521
99831 99471
99871 99443
99774 99442
99709 99426
99988 99421
99785 99420
99620 99417
99771 99399
99933 99398
99816 99...

result:

ok Correct.

Test #7:

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

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
99898 99887
99801 99741
99763 99435
99737 99338
99985 99317
99836 99278
99390 99241
99385 99169
99486 99089
99162 99269
99170 98900
99502 98832
99402 99114
99873 98801
99941 98770
99479 98701
98698 98683
99690 98622
98722 98540
99425 98538
99313 98531
98726 98528
99504 99648
98563 98519
98516 98...

result:

ok Correct.

Test #8:

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

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
99910 99825
99914 99773
99904 99748
99941 99746
99879 99707
99719 99682
99721 99681
99926 99695
99940 99639
99770 99876
99983 99591
99820 99838
99982 99574
99930 99527
99912 99525
99566 99981
99980 99517
99731 99497
99866 99487
99986 99462
99954 99537
99705 99423
99989 99419
99436 99410
99495 99...

result:

ok Correct.

Test #9:

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

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
99950 99980
99921 99910
99972 99895
99912 99892
99958 99869
99915 99868
99873 99867
99840 99835
99893 99832
99916 99821
99969 99823
99842 99811
99880 99807
99918 99806
99854 99805
99977 99800
99853 99787
99956 99780
99798 99906
99894 99863
99959 99825
99924 99758
99858 99737
99813 99734
99841 99...

result:

ok Correct.

Test #10:

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

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
95826 95032
94816 94115
95009 95727
93287 92731
93509 92589
93894 93463
92036 91889
95056 90894
99808 91071
98582 91183
93053 90013
91559 89615
91513 90450
90095 89379
88429 88023
88651 87571
89839 87...

result:

ok Correct.

Test #11:

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

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
98984 75386
88504 74599
88752 71533
84445 68244
85297 67816
99142 65243
96320 62830
86906 60044
92744 98674
95922 59135
98317 59081
78115 58950
83453 58842
89951 58789
81407 58465
86050 58379
90119 57732
79482 57492
93815 57364
98132 57329
92286 96761
89266 55435
81154 55417
94389 55236
91257 54...

result:

ok Correct.

Test #12:

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

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
96138 34081
92038 32638
98752 29917
72048 85530
83793 26741
83390 25594
51571 24746
99253 24514
82889 24053
95659 23435
74140 22917
85624 88551
83536 22420
72975 77529
94752 19261
82174 18687
97204 18226
70452 18213
44737 52816
55957 17672
44191 17603
54382 17412
75040 92630
73788 17061
68179 16...

result:

ok Correct.

Test #13:

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

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
95290 24185
84377 23069
99368 22292
89445 19592
72374 19496
96974 19154
87380 18706
99651 18590
95831 18568
78334 18138
85482 17976
75813 17932
95215 17923
99987 17812
99744 17623
68399 17365
94399 17200
99708 17055
75421 17013
96421 16800
99937 16705
75231 16662
80879 16409
92710 16402
80897 16...

result:

ok Correct.

Test #14:

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

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
96840 7802
95443 5707
99364 5612
82470 5258
67953 4984
92074 4918
96828 4906
94271 4566
92851 4253
92365 95951
85612 4177
75547 4093
99977 4059
89009 4054
76769 3937
80440 3913
82876 3906
63945 82940
97387 3614
92591 3609
81898 97300
92246 3515
56765 3490
75453 78522
66057 3427
85599 3382
65309 ...

result:

ok Correct.

Test #15:

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

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
96706 2267
93600 1484
79300 1309
78139 1269
89109 90885
65492 1226
87298 1204
62078 89056
54647 80577
87384 96099
51801 94915
68475 82132
87425 98136
64953 1091
85731 91261
92548 1057
49779 1041
91147 98921
88328 91941
90647 95875
88522 91502
79496 82759
71064 87202
78623 945
66113 96551
70937 8...

result:

ok Correct.

Test #16:

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

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
95750 824
83464 705
95111 622
92488 614
96448 598
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
97158 481
92920 466
91709 456
94412 455
69375 71375
82066 86414
83493 452
89074 451
86461 92101
97252 99900
...

result:

ok Correct.

Test #17:

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

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: 30ms
memory: 9084kb

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

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

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: 27ms
memory: 8540kb

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: 27ms
memory: 8560kb

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

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

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

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

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: 30ms
memory: 10460kb

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: 24ms
memory: 8920kb

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: 27ms
memory: 10016kb

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: 10ms
memory: 10388kb

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: 44ms
memory: 9500kb

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
99960 99958
99959 99957
99956 99954
99949 99948
99952 99947
99945 99944
99939 99938
99942 99937
99936 99935
99933 99932
99930 99929
99931 9...

result:

ok Correct.

Test #32:

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

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

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
91939 91869
91617 90624
91713 90519
92453 89268
92080 89181
92476 89154
91986 92278
89367 88404
91980 88302
91481 87452
89450 87331
88372 87154
90303 86910
92548 86708
88766 86372
88464 85767
92793 85608
88351 85479
92689 85192
87370 85088
86176 85042
87745 84811
87099 84563
87439 84342
91411 84...

result:

ok Correct.

Test #34:

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

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
91986 91543
91373 91078
91500 90938
91639 90831
91238 90827
91221 90668
91847 90658
91492 90639
91259 90529
91713 90465
90523 90346
90868 89983
90124 89923
90531 89918
91825 89917
91087 89900
90001 89856
91565 89815
91579 89756
91726 89744
89781 89701
90985 89654
92081 89570
90328 89561
91573 89...

result:

ok Correct.

Test #35:

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

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
93242 92922
93224 92472
93244 92396
92279 91744
92740 91546
92260 91453
92405 91416
91620 91351
91284 91273
92145 90951
92844 90812
92048 90764
92909 90703
92180 90407
92734 90358
90766 90320
90887 90317
92424 90302
93359 90208
91671 90068
91173 89905
90396 89894
90128 90849
90340 89794
90962 89...

result:

ok Correct.

Test #36:

score: 0
Accepted
time: 27ms
memory: 9672kb

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
98183 97624
97816 97345
97885 97262
97945 97145
98027 97140
97385 96983
97505 96884
97233 96774
97390 96773
98096 96585
97297 96564
97499 96414
96826 96325
97052 96237
97801 96213
96346 96202
97504 96074
97048 95822
96013 95805
97976 95791
95902 95740
96968 95724
97684 95568
96777 95491
96379 95...

result:

ok Correct.

Test #37:

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

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
25109 25074
25111 24777
25017 24695
25215 24571
24916 24432
24904 24294
25193 24189
24388 24138
24628 24065
25226 24028
24841 23851
24589 23799
24043 23738
24672 23730
24045 23714
24641 23671
24348 23661
24400 23576
24105 23565
24951 23558
24392 23478
23936 23467
24091 23456
24998 23448
23454 23...

result:

ok Correct.

Test #38:

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

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
93191 93190
92972 92822
92914 92750
92708 92629
92781 92569
92847 92006
91984 91801
92766 91527
92391 91525
91819 91431
91706 91337
93240 91254
91761 91246
91199 91107
91753 91097
91242 91083
92358 91014
92884 90890
91589 90887
91118 90823
91173 90804
90797 90754
92524 90677
90825 90612
92165 90...

result:

ok Correct.

Test #39:

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

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
99803 99382
99179 98936
99565 98875
99201 98846
99462 98796
99023 98570
99816 98477
99404 98371
98301 98142
99177 98057
98851 99251
98639 97946
98587 97742
98617 97554
98795 97550
97667 97498
97888 97464
99252 97340
98809 97289
98761 97275
97961 97239
97619 97214
97096 96932
97204 96811
97336 96...

result:

ok Correct.

Test #40:

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

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
91156 90690
91022 90546
91072 90529
91100 90458
90935 90451
90894 90199
91121 90118
90349 90017
90799 89833
90290 89786
90230 89703
91005 89680
91219 89659
91030 89656
90905 89652
90239 89643
90624 89593
90454 89537
89459 89454
89522 89388
90089 89220
90644 89159
90928 89094
90879 89043
89007 88...

result:

ok Correct.

Test #41:

score: 0
Accepted
time: 40ms
memory: 8304kb

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
93253 92655
93452 92469
92776 92264
92804 92236
92124 92080
93209 91729
93102 91547
92681 91505
92346 91492
93327 91361
93105 91016
91732 90984
92187 90889
92379 90852
92111 90808
93408 90753
91642 90710
90933 90588
91163 90540
92246 90533
93196 90526
93034 90374
90705 90359
90890 90312
91572 90...

result:

ok Correct.

Test #42:

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

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
91485 91307
91297 91232
91550 91219
92242 91145
91787 90821
91677 90510
91466 90369
91528 90354
90759 90350
90961 90338
91501 90314
91704 90258
91010 90122
90250 90073
91160 89940
90296 89923
90027 89858
90542 89769
91443 89726
92301 89594
89884 89582
91158 89519
91600 89502
92377 89163
90291 89...

result:

ok Correct.

Test #43:

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

input:

1

output:

YES

result:

ok Correct.