Codeforces Round 192 (Div. 2)


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

Examples
Input
3 4
S...
....
..S.
Output
8
----------------------------------------------------------------------------------------------------
B. Road Construction
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4 1
1 3
Output
3
1 2
4 2
2 3
----------------------------------------------------------------------------------------------------
C. Purification
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
.E.
E.E
.E.
Output
1 1
2 2
3 3
Input
3
EEE
E..
E.E
Output
-1
Input
5
EE.EE
E.EE.
E...E
.EE.E
EE.EE
Output
3 3
1 3
2 2
4 4
5 3
----------------------------------------------------------------------------------------------------
D. Biridian Forest
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5 7
000E0T3
T0TT0T0
010T0T0
2T0T0T0
0T0S000
Output
3
Input
1 4
SE23
Output
2
----------------------------------------------------------------------------------------------------
E. Graph Reconstruction
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
8 7
1 2
2 3
4 5
5 6
6 8
8 7
7 4
Output
1 4
4 6
1 6
2 7
7 5
8 5
2 8
Input
3 2
1 2
2 3
Output
-1
Input
5 4
1 2
2 3
3 4
4 1
Output
1 3
3 5
5 2
2 4
----------------------------------------------------------------------------------------------------
