Codeforces Round 576 (Div. 1)


A. MP3
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6 1
2 1 2 3 4 3
Output
2
Input
6 2
2 1 2 3 4 3
Output
0
Input
6 1
1 1 2 2 3 3
Output
2
----------------------------------------------------------------------------------------------------
B. Welfare State
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
1 2 3 4
3
2 3
1 2 2
2 1
Output
3 2 3 4 
Input
5
3 50 2 1 10
3
1 2 0
2 8
1 3 20
Output
8 8 20 8 10 
----------------------------------------------------------------------------------------------------
C. Matching vs Independent Set
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
1 2
1 3
1 2
1 2
1 3
1 2
2 5
1 2
3 1
1 4
5 1
1 6
2 15
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
Output
Matching
2
IndSet
1
IndSet
2 4
Matching
1 15
----------------------------------------------------------------------------------------------------
D. Rectangle Painting 1
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
###
#.#
###
Output
3
Input
3
...
...
...
Output
0
Input
4
#...
....
....
#...
Output
2
Input
5
#...#
.#.#.
.....
.#...
#....
Output
5
----------------------------------------------------------------------------------------------------
E. Rectangle Painting 2
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
10 2
4 1 5 10
1 4 10 5
Output
4
Input
7 6
2 1 2 1
4 2 4 3
2 5 2 5
2 3 5 3
1 2 1 2
3 2 5 3
Output
3
----------------------------------------------------------------------------------------------------
F. GCD Groups 2
time limit per test: 0.5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
2 3 6 7
Output
YES
2 2 1 1 
Input
5
6 15 35 77 22
Output
YES
2 1 2 1 1 
Input
5
6 10 15 1000 75
Output
NO
----------------------------------------------------------------------------------------------------
