Codeforces Round 381 (Div. 1)


A. Alyona and mex
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5 3
1 3
2 5
4 5
Output
2
1 0 2 1 0
Input
4 2
1 4
2 4
Output
3
5 2 0 1
----------------------------------------------------------------------------------------------------
B. Alyona and a tree
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
2 5 1 4 6
1 7
1 1
3 5
3 6
Output
1 0 1 0 0
Input
5
9 7 8 6 5
1 1
2 1
3 1
4 1
Output
4 3 2 1 0
----------------------------------------------------------------------------------------------------
C. Alyona and towers
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
5 5 5 5 5
3
1 3 2
2 2 1
4 4 1
Output
2
4
5
----------------------------------------------------------------------------------------------------
D. Recover a functional graph
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
0 3
0 3
? ?
Output
2 3 1 
Input
5
3 2
? ?
? ?
? ?
? ?
Output
5 3 2 2 4 
Input
8
? 3
? ?
0 2
0 2
0 3
0 3
0 3
3 3
Output
5 1 4 3 6 7 5 2 
Input
1
? ?
Output
1 
Input
6
0 3
0 3
0 3
0 3
0 3
0 3
Output
2 3 1 5 6 4 
Input
2
1 1
1 1
Output
-1
----------------------------------------------------------------------------------------------------
E. Gosha is hunting
time limit per test: 5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 2 2
1.000 0.000 0.500
0.000 1.000 0.500
Output
2.75
Input
4 1 3
0.100 0.500 0.500 0.600
0.100 0.500 0.900 0.400
Output
2.16
Input
3 2 0
0.412 0.198 0.599
0.612 0.987 0.443
Output
1.011
----------------------------------------------------------------------------------------------------
