Codeforces Round 712 (Div. 2)


A.  Déjà Vu
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
cbabc
ab
zza
ba
a
nutforajaroftuna
Output
YES
cbabac
YES
aab
YES
zaza
YES
baa
NO
YES
nutforajarofatuna
----------------------------------------------------------------------------------------------------
B. Flip the Bits
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
10
0111010000
0100101100
4
0000
0000
3
001
000
12
010101010101
100110011010
6
000111
110100
Output
YES
YES
NO
YES
NO
----------------------------------------------------------------------------------------------------
C. 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
----------------------------------------------------------------------------------------------------
D. 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
----------------------------------------------------------------------------------------------------
E. 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
----------------------------------------------------------------------------------------------------
F. 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
----------------------------------------------------------------------------------------------------
