QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#131000#6396. Puzzle: Kusabisegir187AC ✓44ms33216kbC++174.3kb2023-07-26 02:52:502023-07-26 02:52:53

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-26 02:52:53]
  • 评测
  • 测评结果:AC
  • 用时:44ms
  • 内存:33216kb
  • [2023-07-26 02:52:50]
  • 提交

answer

#include <bits/stdc++.h> //Grzegorz Krawczyk
using namespace std;
typedef unsigned long long LL;
typedef long double LD;
#define rep(a,b) for(int a=0;a<int(b);a++)
#define rep2(a,b) for(int a=1;a<=(b);a++)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
const int INF=INT_MAX/2;
const LL LINF=LLONG_MAX/2;
const int LIM=1e5+7;
/// cd /mnt/c/Users/OEM/staszic-zadanka/wwi2023/taj/prog
///flagi kompilacji:
///g++ -std=c++17 -static -Wall -pedantic -O3 -s -lm -o taj taj.cpp
struct pomocy
{
	int i;
	int lvl;
	char typ;
};
vector<int> G[LIM]; /// krawedzi wychodzace z danego wierzcholka
char type[LIM]; /// typ danego wierzcholka: = musi miec kolege tego samego poziomu, < wiekszego, > mniejszego
vector<pair<int,int>> ans; /// tu trzymam pary wierzcholkow juz sparowanych
pomocy dp[LIM]; /// trzymam kogo "przekazuje" do ojca
bool valid=1; /// czy istnieje odpowiedz
int n;

void debugv(vector<pair<int,int>>& v,string s)
{
	cerr<<s<<": ";
	for(auto [a,b]:v) cerr<<"{"<<a<<","<<b<<"} ";
	cerr<<"\n";
}

void calcdp(int ja,int oj,int cnt)
{
	if(!valid) return;
	/// kazdy vector trzyma nr i glebokosc syna o danym znaku
	vector<pair<int,int>> eq,les,mor;
	
	for(auto a:G[ja]) /// wrzucam swoich synow do wektorow
	{
		if(a==oj) continue;
		calcdp(a,ja,cnt+1);
		if(dp[a].typ=='=') eq.pb({dp[a].lvl,dp[a].i});
		else if(dp[a].typ=='<') les.pb({dp[a].lvl,dp[a].i});
		else if(dp[a].typ=='>') mor.pb({dp[a].lvl,dp[a].i});
	}
	
	/// ----- wrzucam siebie do wlasciwego wektora, potem wszystkie sortuje po glebokosciach -----
	if(type[ja]=='=') eq.pb({cnt,ja});
	else if(type[ja]=='<') les.pb({cnt,ja});
	else if(type[ja]=='>') mor.pb({cnt,ja});
	sort(eq.begin(),eq.end());
	sort(les.begin(),les.end());
	sort(mor.begin(),mor.end());
	
	/// ----- sprawdzam czy sumarycznie musze wypchnac >1 wierzcholek do ojca -----
	if(int(eq.size()%2)+abs(int(les.size())-int(mor.size()))>1)
	{
		valid=0;
		//cerr<<ja<<" w1\n";
		//debugv(eq,"eq");
		//debugv(les,"les");
		//debugv(mor,"mor");
		return;
	}
	/// ----- sprawdzam czy musze wypchnac jakis wierzcholek do ojca bedac korzeniem -----
	if(ja==1&&(int(eq.size()%2)+abs(int(les.size())-int(mor.size()))>0))
	{
		valid=0;
		//cerr<<ja<<" w2\n";
		return;
	}
	
	/// ----- rozpatruje synow z = -----
	for(int i=0;i<int(eq.size())-1;i+=2)
	{
		if(eq[i].st==eq[i+1].st)
		{
			ans.pb({eq[i].nd,eq[i+1].nd});
			continue;
		}
		if((eq.size()%2==0)||(i%2==1))
		{
			valid=0;
			//cerr<<ja<<" w3\n";
			return;
		}
		dp[ja]={eq[i].nd,eq[i].st,'='};
		i--;
	}
	if((eq.size()%2==1)&&dp[ja].i==0) dp[ja]={eq.back().nd,eq.back().st,'='};
	
	/// ----- rozpatruje synow gdy wiecej < -----
	if(les.size()>mor.size())
	{
		for(int i=(int)les.size()-1,j=(int)mor.size()-1;i>=0&&j>=0;i--,j--)
		{
			if(les[i].st<mor[j].st)
			{
				ans.pb({les[i].nd,mor[j].nd});
				continue;
			}
			if(i==j)
			{
				valid=0;
				//cerr<<ja<<" w4\n";
				return;
			}
			dp[ja]={les[i].nd,les[i].st,'<'};
			j++;
		}
		if(dp[ja].i==0) dp[ja]={les[0].nd,les[0].st,'<'};
		return;
	}
	
	/// ----- rozpatruje synow gdy wiecej > lub po rowno <> -----
	for(int i=0,j=0;i<int(les.size())&&j<int(mor.size());i++,j++)
	{
		if(les[i].st<mor[j].st)
		{
			ans.pb({les[i].nd,mor[j].nd});
			continue;
		}
		if(les.size()==mor.size()||i!=j)
		{
			valid=0;
			//cerr<<ja<<" w5\n";
			return;
		}
		dp[ja]={mor[j].nd,mor[j].st,'>'};
		i--;
	}
	if((les.size()<mor.size())&&dp[ja].i==0) dp[ja]={mor.back().nd,mor.back().st,'>'};
	
/*	if(n==1e5&&ja==686)
	{
		cout<<ja<<": "<<type[ja]<<','<<ans.size()<<"\n";
		cout<<eq.size()<<' '<<les.size()<<' '<<mor.size()<<'\n';
	}
	if(n==1e5&&dp[ja].i==68071)
	{
		cout<<ja<<":"<<ans.size()<<','<<oj<<" {"<<dp[ja].i<<','<<dp[ja].lvl<<','<<dp[ja].typ<<"} ";
		cout<<eq.size()<<','<<les.size()<<','<<mor.size()<<'\n';
	}*/
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n;
	rep(i,n-1)
	{
		int a,b;
		string s;
		cin>>a>>b>>s;
		G[a].pb(b);
		G[b].pb(a);
		if(s=="Tong") type[a]='=';
		else if(s=="Duan") type[a]='<';
		else if(s=="Chang") type[a]='>';
	}
	calcdp(1,1,1);
	if(!valid)
	{
		cout<<"NO\n";
		//for(auto [a,b]:ans) cerr<<a<<' '<<b<<'\n';
		return 0;
	}
	cout<<"YES\n";
	for(auto [a,b]:ans) cout<<a<<' '<<b<<'\n';
    return 0;
}

詳細信息

Test #1:

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

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

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

result:

ok Correct.

Test #3:

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

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

score: 0
Accepted
time: 44ms
memory: 10736kb

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

result:

ok Correct.

Test #5:

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

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

result:

ok Correct.

Test #6:

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

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

result:

ok Correct.

Test #7:

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

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

result:

ok Correct.

Test #8:

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

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

result:

ok Correct.

Test #9:

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

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

result:

ok Correct.

Test #10:

score: 0
Accepted
time: 20ms
memory: 11592kb

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

result:

ok Correct.

Test #11:

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

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

result:

ok Correct.

Test #12:

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

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

result:

ok Correct.

Test #13:

score: 0
Accepted
time: 24ms
memory: 10948kb

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

result:

ok Correct.

Test #14:

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

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
2480 84425
90521 97467
3614 97387
2969 3281
3715 3958
3981 4406
4899 4989
5751 8199
8398 9076
9630 10568
11395 12991
13882 17448
17840 18138
18144 20327
24851 31941
34768 35502...

result:

ok Correct.

Test #15:

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

input:

100000
2 1 Duan
3 1 -
4 1 -
5 1 Duan
6 1 -
7 1 -
8 1 -
9 1 -
10 1 -
11 1 -
12 1 -
13 1 -
14 1 -
15 1 -
16 1 -
17 1 -
18 1 -
19 1 -
20 1 -
21 1 -
22 1 -
23 1 -
24 1 -
25 1 -
26 1 -
27 1 -
28 1 -
29 1 -
30 1 -
31 1 -
32 1 -
33 1 Duan
34 1 -
35 1 -
36 1 -
37 1 -
38 1 -
39 1 -
40 1 -
41 1 -
42 1 -
43 1 ...

output:

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

result:

ok Correct.

Test #16:

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

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
336 82705
60220 72014
80211 95022
93125 94029
59250 85950
77242 89854
56243 61755
80147 86382
86818 91748
408 37709
87876 89771
452 83493
481 97158
614 92488
824 95750
377 464
564 569
570 577
624 630
664 722
745 774
775 781
783 793
805 831
837 839
843 865
866 880
895 915
919 921
933 948
954 1007...

result:

ok Correct.

Test #17:

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

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

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

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

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

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: 19ms
memory: 9416kb

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

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

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: 18ms
memory: 10548kb

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

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

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: 14ms
memory: 10892kb

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

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

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

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

result:

ok Correct.

Test #32:

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

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

result:

ok Correct.

Test #33:

score: 0
Accepted
time: 37ms
memory: 10304kb

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

result:

ok Correct.

Test #34:

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

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

result:

ok Correct.

Test #35:

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

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

result:

ok Correct.

Test #36:

score: 0
Accepted
time: 37ms
memory: 10564kb

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

result:

ok Correct.

Test #37:

score: 0
Accepted
time: 11ms
memory: 7264kb

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

result:

ok Correct.

Test #38:

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

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

result:

ok Correct.

Test #39:

score: 0
Accepted
time: 30ms
memory: 10476kb

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

result:

ok Correct.

Test #40:

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

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

result:

ok Correct.

Test #41:

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

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

result:

ok Correct.

Test #42:

score: 0
Accepted
time: 24ms
memory: 10192kb

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

result:

ok Correct.

Test #43:

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

input:

1

output:

YES

result:

ok Correct.