QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#104013#6396. Puzzle: KusabiHe_Ren#AC ✓60ms29952kbC++141.8kb2023-05-08 10:49:222023-05-08 10:49:26

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-08 10:49:26]
  • 评测
  • 测评结果:AC
  • 用时:60ms
  • 内存:29952kb
  • [2023-05-08 10:49:22]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 1e5 + 5;

void No(void){ printf("NO\n"); exit(0);}

vector<int> g[MAXN];
int type[MAXN];

int dep[MAXN];
int f[MAXN];
vector<pii> ans;

void dfs_f(int u)
{
	f[u] = 0;
	for(int v: g[u])
	{
		dep[v] = dep[u] + 1;
		dfs_f(v);
	}
	
	auto upd = [&] (int v)
	{
		if(f[u]) No();
		f[u] = v;
	};
	
	{
		vector<int> id;
		for(int v: g[u])
			if(f[v] && type[f[v]] == 2)
				id.emplace_back(f[v]);
		
		if(type[u] == 2)
			id.emplace_back(u);
		
		sort(id.begin(), id.end(), [&] (int x,int y){
			return dep[x] < dep[y];
		});
		
		for(int i=0; i<(int)id.size(); ++i)
		{
			if(i+1<(int)id.size() && dep[id[i]] == dep[id[i+1]])
			{
				ans.emplace_back(id[i], id[i+1]);
				++i;
				continue;
			}
			upd(id[i]);
		}
	}
	
	{
		vector<int> id;
		for(int v: g[u])
			if(f[v] && (type[f[v]] == 0 || type[f[v]] == 1))
				id.emplace_back(f[v]);
		
		if(type[u] == 0 || type[u] == 1)
			id.emplace_back(u);
		
		sort(id.begin(), id.end(), [&] (int x,int y){
			return dep[x] == dep[y]? type[x] < type[y]: dep[x] < dep[y];
		});
		
		stack<int> sta;
		for(int v: id)
		{
			if(type[v] == 0)
			{
				if(sta.size())
				{
					ans.emplace_back(v, sta.top());
					sta.pop();
				}
				else
				{
					upd(v);
				}
			}
			else
			{
				sta.push(v);
			}
		}
		while(sta.size())
			upd(sta.top()), sta.pop();
	}
}

int main(void)
{
	int n;
	scanf("%d",&n);
	for(int k=2; k<=n; ++k)
	{
		static char tmp[100];
		int i,j;
		scanf("%d%d%s",&i,&j,tmp+1);
		g[j].emplace_back(i);
		type[i] = tmp[1] == 'C'? 0: tmp[1] == 'D'? 1: tmp[1] == 'T'? 2: -1;
	}
	
	dfs_f(1);
	
	printf("YES\n");
	for(auto t: ans)
		printf("%d %d\n",t.first,t.second);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5940kb

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: 0ms
memory: 6020kb

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

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

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

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

result:

ok Correct.

Test #5:

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

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
66693 91216
88445 98194
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
26090 60566
94132 48923
7...

result:

ok Correct.

Test #6:

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

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
2399 2710
3778 3657
3580 2668
2179 2259
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: 37ms
memory: 9268kb

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
105 107
103 117
172 168
275 273
333 321
384 369
327 314
463 433
429 437
588 543
639 667
1273 1167
1375 1160
1176 1117
995 1021
929 926
1059 832
1242 1196
1328 1329
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: 41ms
memory: 9408kb

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
265 266
323 314
309 304
346 343
352 345
338 341
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: 42ms
memory: 9728kb

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
772 773
783 777
830 831
821 824
816 810
845 849
860 858
872 868
895 897
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: 29ms
memory: 10340kb

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
46356 46361
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: 32ms
memory: 8372kb

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

result:

ok Correct.

Test #12:

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

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

result:

ok Correct.

Test #13:

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

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

result:

ok Correct.

Test #14:

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

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
52378 20327
24851 31941
34768 35502
36133 37919
38081 41305
46820 47134
51834 18144
52602 53825
60150 63344
65516 68450
79862 84495
88745 9084...

result:

ok Correct.

Test #15:

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

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

result:

ok Correct.

Test #16:

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

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
86818 91748
37709 408
87876 89771
83493 452
97158 481
92488 614
95750 824
30379 31237
31218 31062
31048 30964
30860 30850
30689 30666
30642 30487
31450 30316
30298 30147
29890 29748
29745 29652
29648 29...

result:

ok Correct.

Test #17:

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

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: 35ms
memory: 8868kb

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

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

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

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

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

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

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

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

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: 32ms
memory: 7916kb

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

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: 25ms
memory: 7876kb

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

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

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

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

result:

ok Correct.

Test #33:

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

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

result:

ok Correct.

Test #34:

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

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

result:

ok Correct.

Test #35:

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

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

result:

ok Correct.

Test #36:

score: 0
Accepted
time: 57ms
memory: 8920kb

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

result:

ok Correct.

Test #37:

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

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
14380 15197
24417 14590
3602 7880
1894 15884
9136 12672
5678 3206
24111 15621
14368 20232
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: 44ms
memory: 8752kb

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
93214 9444
54322 14967
47686 8102
71322 23936
78461 77717
48337 45254
83570 52000
29015 24317
91719 723
63413 35283
3250 89556
60951 81387
50544 76768
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: 52ms
memory: 8964kb

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
37610 77117
30206 19111
70345 88367
36504 20744
75785 43637
79180 14266
83709 26231
55639 85507
10520 3564
21314 11286
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
51349 766...

result:

ok Correct.

Test #40:

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

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

result:

ok Correct.

Test #41:

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

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
42715 63190
20329 10322
70798 78903
45972 14986
62809 83054
52182 1456
62218 19710
85461 84523
52940 12256
31914 7475
39273 86366
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: 42ms
memory: 8656kb

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

result:

ok Correct.

Test #43:

score: 0
Accepted
time: 3ms
memory: 5856kb

input:

1

output:

YES

result:

ok Correct.