QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#104774#6396. Puzzle: Kusabigapinho#AC ✓64ms32304kbC++203.3kb2023-05-11 22:23:522023-05-11 22:23:56

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-11 22:23:56]
  • 评测
  • 测评结果:AC
  • 用时:64ms
  • 内存:32304kb
  • [2023-05-11 22:23:52]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ll = __int128_t;

#define int long long

using ii = pair<int, int>;

#define endl '\n'

const int ms = 1e5+50;
const int mod = 998244353;

int typ[ms];
int lvl[ms];
vector<int> g[ms];
int par[ms];

void dfs1(int u) {
  for(int v : g[u]) {
    lvl[v] = lvl[u] + 1;
    dfs1(v);
  }
}

int solve(int u) {
  vector<ii> lfts[4];
  for(int v : g[u]) {
    int x = solve(v);
    if(x) lfts[typ[x]].emplace_back(lvl[x], x);
  }
  if(typ[u]) {
    lfts[typ[u]].emplace_back(lvl[u], u);
  }
  int sob = 0;
  int lst = 0;
  for(int i = 1; i <= 3; i++) sort(lfts[i].begin(), lfts[i].end());
  for(auto [lv, x] : lfts[3]) {
    if(lst == 0) {
      lst = x;
    } else {
      if(lvl[lst] == lv) {
        par[lst] = x;
        par[x] = lst;
        lst = 0;
      } else {
        if(sob != 0 ) {
          cout << "NO" << endl;
          exit(0);
        } else {
          sob = lst;
        }
        lst = x;
      }
    }
  }
  if(lst) {
    if(sob != 0 ) {
      cout << "NO" << endl;
      exit(0);
    } else {
      sob = lst;
    }
  }
  if(lfts[1].size() == lfts[2].size()) {
    for(int i = 0; i < lfts[1].size(); i++) {
      if(lfts[1][i].first > lfts[2][i].first) {
        par[lfts[1][i].second] = lfts[2][i].second;
        par[lfts[2][i].second] = lfts[1][i].second;
      } else {
        cout << "NO" << endl;
        exit(0);
      }
    }
  } else if(abs(((int) lfts[1].size()) - ((int) lfts[2].size())) == 1) {
    if(sob) {
      cout << "NO" << endl;
      exit(0);
    }
    int canSkip = (lfts[1].size() > lfts[2].size()) ? 1 : 2;
    if(canSkip == 2) {
      reverse(lfts[1].begin(), lfts[1].end());
      reverse(lfts[2].begin(), lfts[2].end());
    }
    int i = 0, j = 0;
    while(i < (int) lfts[1].size() && j < (int) lfts[2].size()) {
      if(lfts[1][i].first > lfts[2][j].first) {
        par[lfts[1][i].second] = lfts[2][j].second;
        par[lfts[2][j].second] = lfts[1][i].second;
        i++;
        j++;
      } else {
        if(canSkip == 0) {
          cout << "NO" << endl;
          exit(0);
        } else if(canSkip == 1) {
          sob = lfts[1][i].second;
          i++;
          canSkip = 0;
        } else if(canSkip == 2) {
          sob = lfts[2][j].second;
          j++;
          canSkip = 0;
        }
      }
    }
    if(canSkip == 1) sob = lfts[1].back().second;
    else if(canSkip == 2) sob = lfts[2].back().second;
  } else {
    cout << "NO" << endl;
    exit(0);
  }
  return sob;
}

void solve() {
  int n;
  cin >> n;
  for(int x = 1; x < n; x++) {
    int i, p;
    cin >> i >> p;
    g[p].emplace_back(i);
    string s;
    cin >> s;
    if(s == "Chang") typ[i] = 1;
    else if(s == "Duan") typ[i] = 2;
    else if(s == "Tong") typ[i] = 3;
  }
  dfs1(1);
  int k = solve(1);
  if(k) {
    cout << "NO" << endl;
    exit(0);
  }
  cout << "YES" << endl;
  for(int i = 2; i <= n; i++) {
    if(par[i] > i) cout << i << " " << par[i] << endl;
  }
}

int32_t main() {
    cin.tie(0); ios::sync_with_stdio(0);
    cout << fixed << setprecision(9);
    int testes = 1;
    // cin >> testes;
    int test = 0;

    while(testes--) {
      // cout << "Case #" << (++test) << ": ";
        solve();
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 6036kb

input:

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

output:

YES
4 5
6 8

result:

ok Correct.

Test #2:

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

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

result:

ok Correct.

Test #3:

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

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

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

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
2 38925
3 90835
5 4737
7 91948
10 75059
12 62351
13 43170
14 22243
16 92645
17 83021
19 92154
20 693
21 3946
22 82765
24 18570
25 3211
29 86603
32 92026
34 73620
35 2350
36 7180
38 9297
39 181
40 99610
41 97678
43 2826
47 31990
48 17732
50 38127
51 55750
55 2855
56 62517
57 27675
58 89545
59 552...

result:

ok Correct.

Test #5:

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

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
24 768
45 1824
81 340
85 128
93 8661
112 685
120 126
138 256
151 874
161 2444
162 226
168 823
206 1489
227 19121
240 269
295 5055
333 1088
334 1878
345 519
351 1721
352 16306
382 614
400 6962
402 1103
407 931
411 61041
420 431
426 2578
435 5819
459 657
477 25610
548 899
562 2378
563 656
594 1759...

result:

ok Correct.

Test #6:

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

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
4 5
6 7
8 9
10 11
12 13
14 15
16 17
18 23
19 20
21 33
22 34
25 26
27 28
29 41
30 45
31 37
32 43
35 36
38 39
40 42
46 48
49 63
50 66
52 53
54 60
55 65
56 57
58 61
59 73
64 68
67 69
70 78
71 79
74 91
75 90
76 82
77 93
80 87
81 126
83 85
84 86
89 94
92 105
95 104
96 112
97 100
98 101
99 114
102 265...

result:

ok Correct.

Test #7:

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

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
10 12
13 14
17 18
26 32
28 30
38 47
51 55
59 70
74 82
80 116
81 85
103 117
105 107
126 131
130 134
133 157
137 141
138 144
139 145
147 156
149 165
151 160
163 181
168 172
169 199
173 189
174 185
179 188
197 216
207 218
211 231
223 255
224 230
233 250
244 247
253 265
260 262
273 275
278 302
279 2...

result:

ok Correct.

Test #8:

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

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
6 10
12 13
15 16
19 23
25 27
31 36
39 44
46 47
52 53
59 62
65 66
68 69
71 74
79 81
82 87
83 92
93 94
98 100
102 105
108 110
112 117
118 120
122 130
132 133
134 142
144 148
155 161
165 168
169 170
171 173
175 178
183 187
194 199
202 207
203 205
212 214
215 217
221 225
223 224
226 232
227 237
242 ...

result:

ok Correct.

Test #9:

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

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
6 9
11 13
14 16
18 20
21 22
24 25
26 29
30 31
33 34
35 38
39 40
42 44
47 49
51 52
53 54
55 56
57 58
59 60
61 62
63 64
66 70
74 77
78 80
81 83
84 86
87 92
93 94
96 98
100 102
107 108
109 110
114 115
116 117
118 121
124 125
126 130
131 134
137 138
144 146
147 152
149 150
155 156
158 162
164 165
16...

result:

ok Correct.

Test #10:

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

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
46 187
379 560
617 664
1104 1599
1692 1891
2060 2120
2231 2560
3050 3072
3156 3161
3406 3700
3934 3939
4116 4338
4326 4581
4758 4774
4915 4986
5196 5281
5384 5513
5677 6435
6536 6606
6570 6738
7012 7037
7170 7289
7658 7686
7894 7922
8110 8465
8862 9157
9716 9769
9829 10261
11025 11281
11644 1257...

result:

ok Correct.

Test #11:

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

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
7 13532
25 14925
46 26513
51 80221
55 97703
58 54135
59 96785
60 31607
65 50980
66 51167
74 48930
77 20592
78 49250
85 58696
90 75655
103 10116
123 13588
131 17852
134 64231
140 3539
150 65239
152 59952
161 13504
163 41781
168 95779
183 7850
196 26470
199 97266
204 73225
205 82213
209 6399
216 5...

result:

ok Correct.

Test #12:

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

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
36 22130
63 54023
76 29790
77 14634
113 12899
132 67715
140 30036
142 31650
175 61760
177 19578
192 14582
196 44274
228 95276
233 30597
236 9551
261 53230
264 41989
270 53197
281 32255
286 23712
317 41102
331 11417
336 21885
350 2306
358 45357
361 31755
373 22317
378 11525
403 21730
404 49344
40...

result:

ok Correct.

Test #13:

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

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
2 40264
3 17313
4 18490
5 23970
6 18192
8 37844
9 24245
11 1036
13 20492
14 5302
15 5383
16 85657
17 63778
19 20720
20 33757
22 18578
23 22927
24 63968
25 32756
26 18517
27 26577
28 12593
29 98530
30 17842
31 39340
33 37110
34 11351
35 61297
36 54473
38 26457
39 9125
40 18427
42 9247
43 44271
44...

result:

ok Correct.

Test #14:

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

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
13 1769
29 6875
32 10200
35 5804
45 53259
53 21405
55 18639
63 70603
72 85141
74 24892
80 9647
81 11975
91 5336
103 29231
104 11497
106 80268
110 85575
111 70189
117 18542
128 25906
135 96765
137 66578
140 45066
144 12955
155 34440
163 28516
164 26563
185 23613
217 2112
221 4492
227 24628
237 66...

result:

ok Correct.

Test #15:

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

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
2 2074
5 2973
33 76201
64 14534
65 97300
75 31363
76 23362
91 41770
92 99053
94 57432
113 34033
119 20107
126 61447
129 81112
141 29634
144 80731
149 42566
151 77178
157 74123
165 3115
168 75009
169 43771
177 89542
203 54362
204 80320
209 35084
212 48876
236 81962
237 76651
261 48550
263 37309
2...

result:

ok Correct.

Test #16:

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

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
2 86064
3 4495
5 23899
7 6325
8 18501
9 8204
10 10249
14 27422
15 52104
16 12737
18 42337
19 53437
20 40829
23 55408
24 15433
25 64924
28 10297
29 74218
31 39136
32 25200
34 21380
36 50196
37 64173
38 31424
40 83372
45 71777
48 98549
50 40739
59 64655
60 28667
64 23804
68 52275
70 95298
74 73617...

result:

ok Correct.

Test #17:

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

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: 38ms
memory: 9980kb

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: 36ms
memory: 10216kb

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

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

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: 38ms
memory: 9644kb

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

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

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: 38ms
memory: 9644kb

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

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: 31ms
memory: 9428kb

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

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

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

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

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
2 4
6 7
10 11
12 13
14 15
19 22
23 24
26 27
28 30
31 33
34 35
36 37
38 39
41 42
43 44
48 49
50 51
53 54
55 56
57 59
60 61
63 64
67 68
69 70
71 73
74 75
76 77
78 79
80 81
83 84
85 87
88 89
90 91
93 94
95 96
98 100
101 105
107 109
110 111
112 114
115 117
118 120
121 122
123 124
125 126
127 128
131...

result:

ok Correct.

Test #32:

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

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
2 71956
12 16
22 38
43 45
50 58
61 62
75 83
96 102
103 107
120 122
124 127
164 172
195 201
203 208
221 233
238 242
251 253
256 257
261 265
270 271
278 285
286 287
300 301
303 317
322 328
330 345
351 378
380 393
394 397
403 405
414 415
422 425
442 444
448 456
460 461
463 484
486 504
510 514
518 5...

result:

ok Correct.

Test #33:

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

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
3 70896
7 26329
10 23726
14 12325
19 70006
23 3126
29 90882
30 26041
38 80827
40 34598
43 9877
44 6175
45 23610
54 17401
59 27190
62 14011
68 75193
70 6197
71 62586
72 916
80 29504
94 36944
96 68799
101 211
105 46048
106 40557
107 17227
110 18165
119 46550
124 4886
126 16194
134 27497
141 60028
...

result:

ok Correct.

Test #34:

score: 0
Accepted
time: 42ms
memory: 9732kb

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
2 13373
4 2357
5 22918
7 28800
8 12
9 87358
10 116
11 59254
13 18
14 394
16 12627
17 3387
19 24546
21 598
22 42602
23 47802
24 81252
25 14864
26 53925
28 87825
29 84
30 8973
31 3444
32 713
33 65424
34 43497
35 52669
36 16042
38 83447
39 59069
40 30268
41 17440
42 62010
43 72748
44 8439
45 18317
...

result:

ok Correct.

Test #35:

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

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
3 64799
4 12828
8 18653
9 45894
15 10640
19 45386
24 3928
26 88017
28 6861
29 81097
30 41422
32 45748
33 12119
34 26014
35 386
36 81840
38 2412
40 14500
45 23369
46 6286
47 49988
48 53164
49 1530
50 1172
51 79884
54 15345
55 481
57 86147
60 707
61 54048
64 3708
66 2972
70 88396
73 52140
74 1083
...

result:

ok Correct.

Test #36:

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

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
2 39340
3 33339
4 89362
5 1500
6 20540
7 58300
8 89096
9 1601
10 46231
11 45736
12 6282
13 90829
14 66093
15 74134
16 20481
17 82626
18 92802
19 92
20 3433
21 1580
22 33656
25 89467
26 82345
27 703
28 23977
29 8493
30 93636
31 40384
32 1286
33 48702
34 42264
35 6279
36 72098
37 17088
38 27365
39...

result:

ok Correct.

Test #37:

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

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
2 39
5 532
6 1283
7 128
8 20916
11 162
12 1149
13 9986
15 50
20 13274
21 131
22 1012
26 16659
30 15967
31 17319
34 13760
35 4011
37 7513
41 17662
43 22457
45 4058
46 6525
49 4443
52 7888
54 107
56 22260
57 11687
58 17450
59 12996
60 21582
62 3951
63 447
64 25093
65 3658
69 20763
70 6828
71 1939
...

result:

ok Correct.

Test #38:

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

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
2 64219
3 73667
4 431
6 65969
7 19736
8 90195
10 1093
11 66838
12 2577
13 11408
14 22450
15 38
16 76232
17 42567
18 11710
19 5360
20 6476
21 6997
22 3416
23 77446
24 92212
25 79812
26 712
27 21182
28 3232
29 923
30 73161
31 61725
32 155
34 5533
35 46
36 86
39 32236
40 29816
41 6050
42 7094
43 79...

result:

ok Correct.

Test #39:

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

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
4 94572
5 89596
6 56
7 10831
9 79601
12 14026
15 29349
16 85991
17 7539
19 22
20 54025
23 99801
24 99638
26 7420
27 2824
31 95462
32 16505
33 85314
36 14345
38 90170
41 79463
42 4047
44 28693
45 64630
46 62027
48 33887
49 16667
51 22281
52 45921
53 31927
54 69
62 22256
63 185
65 31626
70 33987
7...

result:

ok Correct.

Test #40:

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

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
2 51208
3 7
4 1283
5 89938
6 9838
8 2386
9 67427
10 32407
11 62191
12 12449
13 28482
14 65219
15 2521
16 90917
17 72878
18 432
19 34508
20 76357
21 40803
22 13131
23 681
24 141
25 75138
26 61691
27 48056
28 95
29 1136
31 43527
32 59226
33 18565
34 61534
35 66866
36 1436
37 33042
38 52306
39 89
4...

result:

ok Correct.

Test #41:

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

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
5 29409
11 577
14 69743
15 75817
18 1069
21 19923
24 90631
25 2935
26 39111
29 81046
35 54512
36 70772
38 2082
40 55885
42 56411
44 19825
52 74647
53 5491
55 7505
56 82545
58 81897
60 2420
61 87626
64 18765
65 29582
66 5478
69 76855
71 30166
72 79913
74 74755
75 55488
78 65109
82 27560
83 83057
...

result:

ok Correct.

Test #42:

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

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
2 64125
4 77137
5 10
7 77941
9 552
12 1585
14 15
16 36491
17 46105
18 36744
19 14129
21 26651
23 30183
26 792
27 89263
29 5090
30 9617
33 5135
34 67281
35 5775
36 1345
38 59681
39 60642
40 130
41 66458
42 78605
46 75388
47 914
49 14635
51 63
52 42024
53 645
54 2838
55 46470
57 28775
58 17263
60 ...

result:

ok Correct.

Test #43:

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

input:

1

output:

YES

result:

ok Correct.