Educational Codeforces Round 125 (Rated for Div. 2)


A. Integer Moves
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
8 6
0 0
9 15
Output
1
0
2
----------------------------------------------------------------------------------------------------
B. XY Sequence
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
5 100 1 30
7 1000000000 1000000000 1000000000
4 1 7 3
Output
15
4000000000
-10
----------------------------------------------------------------------------------------------------
C. Bracket Sequence Deletion
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
2
()
3
())
4
((((
5
)((()
6
)((()(
Output
1 0
1 1
2 0
1 0
1 1
----------------------------------------------------------------------------------------------------
D. For Gamers. By Gamers.
time limit per test: 4 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 10
3 4 6
5 5 5
10 3 4
3
8 3
5 4
10 15
Output
5 3 -1 
Input
5 15
14 10 3
9 2 2
10 4 3
7 3 5
4 3 1
6
11 2
1 1
4 7
2 1
1 14
3 3
Output
14 4 14 4 7 7 
Input
5 13
13 1 9
6 4 5
12 18 4
9 13 2
5 4 5
2
16 3
6 2
Output
12 5 
----------------------------------------------------------------------------------------------------
E. Star MST
time limit per test: 6 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3 2
Output
5
Input
4 4
Output
571
Input
6 9
Output
310640163
Input
42 13
Output
136246935
----------------------------------------------------------------------------------------------------
F. Words on Tree
time limit per test: 9 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
3 2
2 3
2 1
2 1 ab
2 3 bc
Output
YES
abc
Input
3 2
2 3
2 1
2 1 ab
2 3 cd
Output
NO
Input
10 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 2 ab
1 3 ab
1 4 ab
1 5 ab
1 6 ab
1 7 ab
1 8 ab
1 9 ab
1 10 ab
10 2 aba
Output
YES
baaaaaaaaa
Input
10 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 2 ab
1 3 ab
1 4 aa
1 5 ab
1 6 ab
1 7 ab
1 8 ab
1 9 ab
1 10 ab
10 2 aba
Output
NO
----------------------------------------------------------------------------------------------------
