QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#408682#3487. Tree Hugginge3c8f1a924AC ✓118ms20432kbC++142.2kb2024-05-10 21:15:542024-05-10 21:15:55

Judging History

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

  • [2024-05-10 21:15:55]
  • 评测
  • 测评结果:AC
  • 用时:118ms
  • 内存:20432kb
  • [2024-05-10 21:15:54]
  • 提交

answer

#include<iostream>
#include<vector>
#include<queue>
std::vector<int> e[100005], re[100005];
int n, f[100005], U[200005], V[200005], w[100005], d[100005];
int vis[100005];
void getW(int u) {
	static int vis[100005];
	for (int v : e[u]) {
		if (vis[v] != u) vis[v] = u, w[u]++;
	}
}
void bfs(int u) {
	static std::queue<int> q; q.push(u);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		if (vis[u]) continue; vis[u] = 1;
		int c = 0;
		for (int v : e[u]) {
			if (f[v]) c += (f[v] == u);
			if (f[v]) continue; f[v] = u, c++;
			for (int w : re[v]) if (!vis[w]) q.push(w);
		}
	}
}
void build(int u) {
	static int occ[100005];
	static std::queue<int> q;
	while (!q.empty()) q.pop();
	q.push(u); int fl = 0;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		if (vis[u]) continue;
		int c = 0;
		for (int v : e[u]) if (occ[v]) c++;
		if (c == 2) {
			for (int v : e[u]) {
				if (!occ[v]) continue; f[v] = u;
				static std::queue<int> Q;
				for (int w : re[v]) if (vis[w] == 1) Q.push(w);
				while (!Q.empty()) {
					int u = Q.front(); Q.pop();
					if (vis[u] != 1) continue;
					vis[u] = -1;
					for (int v : e[u]) {
						if (f[v]) continue; f[v] = u;
						for (int w : re[v]) if (vis[w] == 1) Q.push(w);
					}
				}
				break;
			}
			fl = 1;
		}
		vis[u] = 1;
		for (int v : e[u]) {
			if (occ[v]) continue;
			occ[v] = 1;
		    if (fl) f[v] = u;
			for (int w : re[v]) if (!vis[w]) q.push(w);
		}
	}
}
int ans[200005], g[100005];
int main() {
	std::cin >> n;
	for (int i = 1; i <= 2 * (n - 1); i++) {
		std::cin >> U[i] >> V[i];
		e[U[i]].push_back(V[i]), re[V[i]].push_back(U[i]);
	}
	for (int i = 1; i < n; i++) getW(i), d[i] = e[i].size();
	for (int i = 1; i < n; i++) {
		if (vis[i] || w[i] != d[i] - 1) continue;
		bfs(i);
	}
	for (int i = 1; i < n; i++) if (!vis[i]) build(i);
	for (int i = 2; i <= n; i++) if (!f[i]) return std::cout << "impossible\n", 0;
	for (int i = 1; i <= 2 * (n - 1); i++) {
		int u = U[i], v = V[i];
		if (f[v] == u) ans[i] = 1, f[v] = 0;
		else if (g[u]) return std::cout << "impossible\n", 0;
		else g[u] = v;
	}
	for (int i = 1; i <= 2 * (n - 1); i++) std::cout << (ans[i] ? 'L' : 'R');
	std::cout << std::endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
1 2
2 5
2 3
1 3
3 5
4 5
3 4
1 3

output:

LLRLRRLR

result:

ok 

Test #2:

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

input:

3
1 2
1 2
1 3
1 3

output:

impossible

result:

ok 

Test #3:

score: 0
Accepted
time: 105ms
memory: 19680kb

input:

100000
47469 47470
72550 72551
31535 81534
49832 99831
86776 86777
12769 12770
39146 89145
14425 14426
35647 85646
90570 90571
77055 77056
30465 80465
82785 82786
88530 88531
50015 50016
96964 96965
45984 45985
47158 97158
98106 98107
1818 51817
31919 81919
25944 75943
17755 17756
26979 76978
56457 ...

output:

LRRRRLRLRRRLRRRRLLRRLRLRRRRLLRRRRLLRRLLRRLRRRLLRLLLRLRLLLRLLRRRRRRRRRRLRRLLLRLLRRRLRLLLLRRRRLLLRRRLLRRLRRRLLRRRRLLLLRRLRRLLLLLLLLRRLRLRRLLLRRLLLRRRLRRLRLLRLRRRLRRRRLRLRLRLRRLRLLRRRRRRLRLRRRRRLRRRRRLLLRRLLLRLLRLRLRLLRLLLLRLRLRLLRLLLRRLRRRLRRRRLLLRLLLRLLRRLRRLRLLLRLRRRRLRLRRLRRRRRRRLRRLRRRLLLRLRLLLLLR...

result:

ok 

Test #4:

score: 0
Accepted
time: 114ms
memory: 19756kb

input:

100000
1076 1077
2943 97058
45917 54085
42045 57957
27241 27242
23988 76014
15779 15780
64542 64543
32281 67721
1554 98448
27238 72764
35657 35658
7930 7931
47944 52058
49192 50810
20775 20776
15387 84615
57245 57246
6502 6503
41974 58028
65744 65745
8014 91987
42101 42102
18676 81326
41951 58050
26...

output:

LLRRLRLRRRRLLRRLRRLRRLLRLLRLLRLRLRLLRLLRRRRLLLLRLRRRRLRLLLRRRRLLLLRLLLRRLRLRLRLRLRRRRLRRLRLRLLRRRLRLLRRLRRLRLRRLRLRLLRLLLRLLRRRLRRRLRLLRLRRRLRRRRRRLLRRRLLRLLLRRLRLRRLRLLLLRRLRRRRLLRLRRRLRRRLLLRRRLRRLRRRRRRLRLLRRRRRLLRLLLLRRRRRLRRRRRRRLRLRRLLRLLLRRLRLRLLRLLLRRRLRRLLRLRRLRLRRRLLRLRLRRRRRRRLLRLRLLRRLLR...

result:

ok 

Test #5:

score: 0
Accepted
time: 118ms
memory: 19520kb

input:

100000
77675 77677
69316 69317
34082 34084
98715 98717
86710 86711
45509 45510
60814 60815
3829 3830
95894 95896
42710 42711
84428 84429
24015 24017
94638 94640
61396 61397
25642 25643
68450 68451
75513 75515
73310 73311
31526 31527
82360 82361
81399 81401
17066 17067
71709 71710
635 636
77378 77380...

output:

RLRRLLLLRLLRRLLLRLLLRLLLRRRRRRRLLLLLLRLLRLRRLRLLLLRLLRRRRLRRLLLLLRLLRRRRRRRRRLLRRLLLRLRRLRLLLLRRLLLLLRLLRLRLLLLRLLRLLRRRRRLRLLRRLLLRRRRRLRRRRRRRRRLLRLLRRRRLLLLLRRRLRLRLLLRRRLLLLLLLRRLLLRLLLRRLLRLRRRRRLRRLRLRLRLRLRRLRRLRLRRLLLLRLRRLLRRLLRRRRRRRRRLLLLRRLRLLLLRRRLRLLRLRRRRLLLRLLLLLLLRLRLLLLRLLLRRLRRRRR...

result:

ok 

Test #6:

score: 0
Accepted
time: 117ms
memory: 19736kb

input:

100000
96292 96307
98393 98394
14849 14974
503 1000
4787 4788
42163 42164
47430 47874
2477 9905
33783 45478
29141 29191
46228 46229
48667 48668
32799 34015
34688 34689
22354 22355
4489 44498
19925 25001
47669 66799
86848 86891
92079 92867
39864 39868
14528 14529
7424 55462
78879 78885
12790 12795
62...

output:

LLLRRLLRRRLLRLLLRRRRRLLRLLRLLRRLLRRLLLRLLRRLLRRLRRRLRLLRLRRLRLRRLLRRLLRLLRLRLRRLRLRRRRRLLLLLRRRRLRRRLLRRLRRLLRRLLRLLLRRRLLLRLRLRLRLRRLRRRLLLRLLLLLLLLRLRLRRRRLRRLRRLRLRLRLRLRLLLLLLLLLRLLLLLLRLLLLLLRRRRLLLRLLLRLRLRRRLRRRLRRRLLLLRLRLLLLRRRLLLLRRRLRRRRLRRLLLRLLLLLLLRRLLRLLRRLLRLRLLLRRLLLRLLRLRRLRLLRRRRL...

result:

ok 

Test #7:

score: 0
Accepted
time: 107ms
memory: 19388kb

input:

100000
94448 94454
47649 47650
17619 17620
15007 15008
87119 87121
33405 33408
92906 92907
20228 20229
83686 83687
52569 52574
56130 56131
85052 85053
34030 34031
61884 61885
51332 51334
10837 10838
42167 42168
5550 5551
19339 19341
13455 13456
8105 8106
82931 82932
4904 4905
21197 21198
45197 45198...

output:

RLLLRRLLLRRLLRLLLLLLLLLLLRLLLLLRLLRLLLLLLLRLLRLLLLLRRLLLLLRLLLLLRLLLRLLLRLRLLLLLLLLLRLLLLLLRLLLLLLLLLLLRLRLLLLRLLLLLLLLLLLLLLLLLLRRLLLLLLLLRLRRLLLLLLLLLLLRLRLLLLLLLLLLLLLLLRRLLLLLLLLLLLLLLLRLLLLLLLLLLLLRLLLLLLRLRLLLLLLLRLLLRLLLLLLRLLLLLRLRLLLRLRLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLRLLLLLLLRLLLLLLLRLLLLLLL...

result:

ok 

Test #8:

score: 0
Accepted
time: 105ms
memory: 18576kb

input:

100000
2381 47533
25141 95781
11273 17367
55442 66919
65505 91625
46416 47639
53011 88444
34262 46485
36811 49222
13273 29214
64629 65257
90406 90946
34938 84427
78267 89692
46093 87006
700 4024
1981 49824
9113 22336
14428 80864
71237 73951
15237 85899
6366 87542
17416 87910
19236 23987
42507 45242
...

output:

impossible

result:

ok 

Test #9:

score: 0
Accepted
time: 109ms
memory: 19364kb

input:

100000
46508 46509
77335 77336
77276 77277
22617 22618
44049 44050
31746 31747
52565 52566
98082 98083
31739 31740
40139 40140
14963 14964
77596 77597
89939 89940
19879 19880
15053 15054
6883 6884
44109 44110
63958 63959
23425 23426
82477 82478
54066 54067
63683 63684
54627 54628
92307 92308
96064 9...

output:

LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL...

result:

ok 

Test #10:

score: 0
Accepted
time: 99ms
memory: 19596kb

input:

99999
83336 99999
70928 70929
35724 35725
35438 99999
34822 34823
75605 99999
35429 99999
35817 35818
29996 99999
87124 87125
91143 99999
18082 18083
15731 99999
82065 82066
34205 99999
90435 90436
25357 99999
98198 99999
6647 6648
17671 99999
33423 33424
33232 99999
95685 95686
98553 98554
89505 99...

output:

RLLRLRRLRLRLRLRLRRLRLRLLRRRLRRLRRRRRRLLRLLLRRLLRLRLRLRRLLRLLRRLRRRRLLRRLLRLRLRLLLLRLRRRRRLLLRRLRLRLLRRRRRRLRRRLRRRRLLRLLRRLRLRLLRLLRRRRLLLRRLLLRRRLRLRRLRRRLLLLLRLRRLRRLLRRLRRRRRLLLRLLLRLLLLLRRLLRLRRLLLRLLLRLRLRRLLLLLRRRLLLLRRLRLLLRLLRRRRLRLLLLRLRRLLRRRRLRLLLRRRLRRLLLRLRRLRRRLLRLRLRRRLRRLRRLLRRLRLRRR...

result:

ok 

Test #11:

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

input:

2
1 2
1 2

output:

LR

result:

ok 

Test #12:

score: 0
Accepted
time: 116ms
memory: 19336kb

input:

100000
6422 6423
7078 39700
93461 93462
27117 27118
1396 21159
62146 98369
2924 72492
19070 56178
83957 83958
25611 74696
1963 4411
6461 30374
30792 46421
19569 19570
37360 37361
7769 58763
48988 48989
9368 9369
90046 90047
17648 35317
77834 98231
10891 10892
13742 13743
52496 52497
51518 58861
9745...

output:

RLRRLLLLRLLLLRRLRRRLLRRRLRRLLRLRLRRRLLLRRRLLRLRRLLLRRLRRLLRRRLLLLRRRRRLLRRLLRLRRLRRRRRLRRLRLRRRRRLLRLRLRRLRRLRLLLLRRLLRLRRLLRLLRRLRLLRRLLRRRRLLLRLRLLRLLLRRRRRRRLLRLRLLLRLLRRLRLLLRRLLRRLRRLRRRLLLRRRRRLRLRRLRLRLRRRLLLRRRRLRLLLLRRLRRLLRRLLLLLRRLLRRRRRLRRLLLLLLLLLLLLLLRRRRRLLRRLRRLRRRLLRLLRRLLLLLLLLLLLR...

result:

ok 

Test #13:

score: 0
Accepted
time: 110ms
memory: 19680kb

input:

100000
50086 100000
15167 100000
30459 100000
67484 100000
39503 56272
1071 94916
58638 69938
68098 100000
21983 100000
11622 14147
22249 60478
41488 82578
3500 52437
65182 83813
93200 100000
63203 100000
48058 100000
33261 68066
31016 100000
15508 100000
43807 44313
29248 50826
89864 100000
27632 1...

output:

RRRRLLLRRLLLLLRRRLRRLLRRRLLRLRLRLRRRRLRRRLRRRRLRLRLLLLLRRRLLRRRRLRLRLRLRRRLLLRRRLRLLLRLRRLLRRRRLRRLRLRLRLLRLLRLRLRLRLRRRRLLRLLLRRLLRRRRRRLLRLRRRRLRLLLRRRLLLRRRLRRRRLRRRRRRLRRRRLLLRRRRLRLRRRRRRRRRRLLLLRLRLLLRRRRRLLRLLLRRRLRLLLRRRRRRRLLLRRLLLLLLRRLRLRRRRLRRRLRRRRLLRLLLRLRRRRRLRLRLRRLLRLRLRLLRLRRRLRLLL...

result:

ok 

Test #14:

score: 0
Accepted
time: 106ms
memory: 19504kb

input:

100000
2 5218
19231 19232
86206 86208
27041 27045
85 81569
892 1517
5235 76982
37663 37664
63659 63660
6681 39613
76040 76041
62153 62154
17460 19496
57854 57856
556 45489
71851 71852
1 98584
6315 73301
79186 79187
79246 79247
88054 88055
1186 93355
21193 76999
98734 98735
26259 97482
5466 21033
825...

output:

LRRRLLLRRLRRLRLRLLRRRLLRLLRRLRLLLRRRLRLRLRRRRLLRLLRRLRLLLLLRLRLRRLLLRRRLLLRLLLLLLRLLLRRRRRRRRLRLLRRRRLLRLLRLLRRLLRLLRLRRRLLRLLRLRRRLLRLLLLLRLLLRLLRRLRRRRLRRLLLLLRLLRRLRRRRRLLLLLLRRRLLLLRRLLLRLRLLRLLLRRLRRRRLLLRRRRLLLLRLLRRRRLLRLLLRRLRRLRLLRRRRLLRRLRLRRRRRRRRLLLLRLLLRLRLRRRRLRRLLRRLRLLRRRLLLLLLLRRLLR...

result:

ok 

Test #15:

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

input:

100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100...

output:

impossible

result:

ok 

Test #16:

score: 0
Accepted
time: 81ms
memory: 18484kb

input:

100000
41481 41482
1 100000
1 100000
64764 64765
1 100000
74864 74865
1 100000
79291 79292
1 100000
74858 74859
1 100000
1 100000
1 100000
1 100000
1 100000
86185 86186
1 100000
1 100000
88382 88383
20521 20522
1 100000
1 100000
89294 89295
84622 84623
35836 35837
1 100000
1 100000
1 100000
78143 78...

output:

impossible

result:

ok 

Test #17:

score: 0
Accepted
time: 110ms
memory: 18688kb

input:

100000
75512 75948
22097 56503
16704 41097
8821 20215
61008 82951
3936 43483
15777 21310
1582 8695
13665 72095
32229 90726
56968 86898
11425 20827
43217 81626
15487 91245
50300 63769
36159 93147
20288 31345
59424 69536
25666 48834
48128 56700
51320 65242
83822 93136
26628 47095
34546 83371
20205 324...

output:

impossible

result:

ok 

Test #18:

score: 0
Accepted
time: 118ms
memory: 17684kb

input:

100000
65216 83882
10700 63639
33928 72339
41323 77996
7772 56609
22322 44021
13832 62351
65111 86196
34089 64808
12724 48696
77257 91671
49668 64008
10838 16441
70535 98188
26701 88875
43101 76155
80614 91617
57658 97040
46136 60648
23470 39189
71759 80192
47185 66448
38160 79179
15508 17182
4486 3...

output:

impossible

result:

ok 

Test #19:

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

input:

3
1 3
1 2
2 3
1 2

output:

LLRR

result:

ok 

Test #20:

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

input:

4
3 4
2 3
1 4
3 4
1 2
2 4

output:

LLRRLR

result:

ok 

Test #21:

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

input:

5
3 4
4 5
1 2
2 4
2 5
1 3
2 4
3 5

output:

impossible

result:

ok 

Test #22:

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

input:

6
1 2
3 5
2 3
3 4
1 2
4 5
1 5
1 3
5 6
2 6

output:

LRRLRRLLRL

result:

ok 

Test #23:

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

input:

10
4 10
5 7
1 3
5 9
2 4
2 8
7 9
9 10
7 8
4 5
1 2
3 4
4 7
8 10
8 10
1 4
6 8
1 6

output:

RRLLLRRRLLLRLLRRRL

result:

ok 

Test #24:

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

input:

3
1 2
2 3
2 3
2 3

output:

impossible

result:

ok 

Test #25:

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

input:

5
2 5
1 4
3 4
2 3
4 5
3 4
2 4
2 3

output:

impossible

result:

ok 

Test #26:

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

input:

10
1 10
2 10
2 5
4 5
7 8
1 8
4 9
2 7
5 6
2 9
5 6
9 10
4 9
8 10
8 9
5 7
2 8
2 8

output:

impossible

result:

ok 

Test #27:

score: 0
Accepted
time: 111ms
memory: 19740kb

input:

100000
27350 92210
14491 23156
9744 21697
39108 88751
98405 98481
14607 70817
72482 74343
9230 16633
41110 58865
81008 97777
27588 98983
51533 74299
5897 7472
817 4483
46069 55808
7497 31583
6934 25452
2939 6466
87295 90390
17488 42427
84329 97327
78129 90515
5000 8088
45388 73563
40863 71872
58611 ...

output:

LLRLRLRLRLRLLLLLLLRRRRLRLRLLLLLLRLRLLLRLLRLLRRRLLLLRLRLRLRLLLLLRLLRRLRRRLLLLLRLRLLRRRLLRRRRRRLRLRLRRRRRLRRRLLRLLRLLLLRRLLRRRRLLRLLRRLLRRRRRRRRLLRLLRRRLLRLRLLLRLRRLRRRRRRLRRLRRRRLRRLRLLLRRRRRLRLLLRLLLLRRRLLLLLLRRLLRLRRRLLLRLRLRLRRRLRRLLRRRLLRLLLRRLRLLLLLLRRLLLLRRRRRRRLRRRLRRRRRLLRRRRRRRLLLLLRLLLLLLLL...

result:

ok 

Test #28:

score: 0
Accepted
time: 97ms
memory: 20300kb

input:

100000
2249 79976
13961 100000
19855 94202
87563 99994
4998 56354
1 64913
529 79789
1 57928
834 90631
762 49896
4529 54571
95563 99642
1 61718
61963 77047
37601 42447
11502 100000
1 18669
21244 74628
99738 99788
3042 48944
11267 36782
2677 40755
24444 82628
35616 61377
17069 61074
64846 89569
11320 ...

output:

LRLRRLLLLLLRLLLRLLRLLLLRRRRLLLLLRRRRRLRLLRLLLRLLLLLRLRLRRRRLRRLRRRRRLLRLLRRLLRRLRRRRRRRLLRLRLRRLLLLLRRLRLRLLLRRLLLRRRLLLLLRLRLRRRRLLRRLLRLRLRRLLRRRRRLRRLLLLLLLRLRLRLLRRLRRRLLLLRLLRRLLRLLLLLLRLRRLRLLRLLLLLRRLRRRLLLLLRRLRLRRLLRRRLRRRRRRLLRLLRRLRLLLRLLLLRLRRRRRRRLRRLRRRRRRLLLLLRRRRRLRRLLRLRRLRLRLRRLRLR...

result:

ok 

Test #29:

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

input:

10
9 10
6 8
2 5
7 9
5 9
1 2
3 4
6 7
4 6
8 10
2 10
2 4
3 5
6 7
5 8
1 4
2 3
2 6

output:

RLLRLLLLRRLRRRRRLL

result:

ok 

Test #30:

score: 0
Accepted
time: 93ms
memory: 19628kb

input:

100000
4240 4241
1 79621
13881 13882
47633 47634
10968 10969
66231 66232
1 23932
1 34541
21621 21622
82534 82535
1 38763
1 20444
1 85833
1 21191
1 80696
1 36385
1 29117
1 23344
1 49716
25503 25504
8649 8650
1 30912
1 70217
96380 96381
93723 93724
85983 85984
55910 55911
45457 45458
1 35485
1 67815
7...

output:

RLRRRRLLRRLLLLLLLLLRRLLRRRRRLLRLLRLLLRRRRLRRLLRRLLRRLLLRLRLLLRRLRLLRLLLLLLRLRRLRRLRRRLLLRLRLRLLRRLLLLRLLRRRRRRLRRRRLRLRRRRRRRRRRRRRRRLLRRRLRRLRLLRLRRLLRRLLRRLLRRLLRLLRRLRLLRLRLLLLLRLLRLLLRRRRLLLLLLRLRRLLRLLRRRRRRLRRLRLLRRLLLLRRLLRRRRLRRLLLLRRLLLRLLLRRLLLLLRRRLLRLRLLLLRRRRRRRRRLRLLRRLRRLLLLRRRRRLLLLR...

result:

ok 

Test #31:

score: 0
Accepted
time: 91ms
memory: 20000kb

input:

100000
94129 100000
1 46711
44270 100000
73986 100000
88815 100000
19313 100000
1 66780
1 36436
26216 100000
1 51814
60035 100000
34482 100000
54358 100000
58711 100000
1 90858
42027 100000
77079 100000
20417 100000
1 24540
1 58259
53847 100000
1 22420
1 81169
10125 100000
47110 100000
1 35323
49939...

output:

RLRRRRLLRLRRRRLRRRLLRLLRRLRRLRLRLLLLLRLLLRLLLLRRLLRRLRRRLLRLLLLLRLLRLLLLRLRRLLRLRRLRLRRLLRLRRLRLLLRRLRLRRRLRRLRRLRRRLLLLLLRLLLLRRRRLRRLLRLRRRLLRLRRLRLLRLRLLRRRLRRRRLLRRRRRRLRRLRRRRLLRLRRRRRRLRLRRRRLRRRLLLRRLLRLLRLRLRRLRRRRRLLRRLRRLRLRRLRRLLLRLRLLLRRRLLRLRRLRRRLRRLRLLLLRRRRRLLLLLRLRRRRLRLRRLRLLLRLLRR...

result:

ok 

Test #32:

score: 0
Accepted
time: 110ms
memory: 19072kb

input:

100000
75076 97931
13481 99996
9048 22790
1386 21510
34374 99915
15695 28380
49563 100000
88772 98320
70943 98943
90579 99995
91902 97555
19692 99245
176 50222
639 54152
20021 53997
26057 99731
1731 97958
42255 99533
1 58016
44818 63589
89 8080
37619 65158
92419 99986
51469 99414
79 45936
83025 9664...

output:

impossible

result:

ok 

Test #33:

score: 0
Accepted
time: 103ms
memory: 18944kb

input:

100000
11224 99948
84266 92944
3571 64098
12003 99995
23796 98299
38490 99159
12298 83375
62445 76226
11435 61627
75811 99987
1325 17993
179 60917
53 22669
3 73363
14766 98022
59211 84239
37779 95062
94218 96316
12029 91234
1 83796
2486 84822
1939 7073
46973 99575
1452 88901
1721 42452
88887 100000
...

output:

impossible

result:

ok 

Test #34:

score: 0
Accepted
time: 109ms
memory: 19776kb

input:

100000
86737 94241
74442 88025
21860 30351
27323 54968
56625 93748
26310 59683
29643 72604
3539 40059
16427 25834
1903 4083
16367 97219
2979 3435
96170 97892
8270 23194
42526 79637
33350 92850
70120 70324
15496 31447
81274 93729
12990 58047
17771 68602
31891 33024
70653 86438
49885 82835
30157 91311...

output:

RLLLLLRLRLRLRLRRRRRLRLRLRLLRLLLRLRLRLLLRLRRLLLLRLRRRLLRLLLRLLRRLRRRRLRLLLLLRLRRLRLRRLRRRRLLLRRLLLLRRRLLRLRLLRRLLLRRRRRLRRRRLLLLRLRRLRLLRLRLRLRRLLLLLRLRRRRLLRRRLRLLLLLRRRRLLLRRRLLRRLLRLRLRRLLRLRRRLRLRRRLLRLLRRLLLRLLLLRLRLRLRRLLLLRRRLRRLRRRLLLRRLRLLRLLLRLLLRLLLRRLRLRRRLRRRRLRRRLLLRRRRRLRRRLLLLLRLRRRRR...

result:

ok 

Test #35:

score: 0
Accepted
time: 99ms
memory: 20432kb

input:

100000
3738 86984
4742 73810
18 28861
401 91200
7359 96567
48912 90346
22310 99696
1 94714
1 3406
27197 83787
71 70108
75206 99999
1 82541
8592 85019
1435 52147
1579 2279
287 76125
64295 89846
14933 69998
17276 86842
1142 61675
4145 89912
5153 50296
6 53424
62767 90762
2 96979
84701 100000
2761 3648...

output:

LRLLRLRLLRLRLLLLRRRRLLLLRLRLLLRRRRRLRRLRLRRLRRLRRLRRLRLLRRRRLLLLLLRLLRLLRLRRLLLLRLLRRLRRLLRRLRLRLRLLRLLRLRRRLLLRLRRLLLLRLLLLLRRLLRRRRLRRRLRRRLLRLLLRLLLLLLLLRRLRLRRRRRLLLRRLLRRRLRLLLLRRLRLLLLLRRLRLLLRLRLLLLLRLLLRRLLRRRLRRRRLLLRRLRRLRLLLLRRLRLRLRLLLLRRLLLLRRLRLRRRLLLLRLLLRRLRRRLRRLLRRRRLLLRRLRRRRRRLRR...

result:

ok 

Test #36:

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

input:

5
3 5
1 2
4 5
2 3
2 4
3 5
1 5
2 4

output:

LLRLLRRR

result:

ok