Codeforces Round 712 (Div. 1)


A. Balance the Bits
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
6
101101
10
1001101101
4
1100
Output
YES
()()()
((()))
YES
()()((()))
(())()()()
NO
----------------------------------------------------------------------------------------------------
B. 3-Coloring
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2
1
2
1
3
Output
2 1 1
3 1 2
3 2 1
1 2 2
----------------------------------------------------------------------------------------------------
C. Travelling Salesman Problem
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
1 9
2 1
4 1
Output
11
Input
6
4 2
8 4
3 0
2 3
7 1
0 1
Output
13
----------------------------------------------------------------------------------------------------
D. Flip the Cards
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
3 10
6 4
1 9
5 8
2 7
Output
2
Input
2
1 2
3 4
Output
-1
Input
3
1 2
3 6
4 5
Output
-1
----------------------------------------------------------------------------------------------------
E. 2-Coloring
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2 2
Output
2
Input
4 3
Output
294
Input
2020 2021
Output
50657649
----------------------------------------------------------------------------------------------------
F. Balance the Cards
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
1 3
-3 -5
4 -3
2 2
-1 -4
-2 5
3 -1
5 1
-4 4
-5 -2
Output
YES
1 3
4 -3
-4 4
-1 -4
5 1
3 -1
2 2
-2 5
-3 -5
-5 -2
Input
2
1 1
-1 2
2 -1
-2 -2
Output
NO
----------------------------------------------------------------------------------------------------
