import java.util.ArrayList;
import java.util.List;
public class OddEvenTreeHard {
int[] col;
boolean bad;
void dfs
(int cur,
int to,
String[] dist
) {
if(col[cur] == -1)
{
col[cur] = to;
}
else
{
if(col[cur] != to) {
bad = true;
}
return;
}
for(int i = 0; i < dist.length; i++)
{
if(dist[cur].charAt(i) == 'E' || dist[i].charAt(cur) == 'E')
dfs(i, to, dist);
if(dist[cur].charAt(i) == 'O' || dist[i].charAt(cur) == 'O')
dfs(i, 1-to, dist);
}
}
public int[] getTree
(String[] dist
) {
int[] noSolution = new int[1];
noSolution[0] = -1;
int n = dist.length;
col = new int[n];
bad = false;
int currentCol = 0;
for(int i = 0; i < n; i++)
col[i] = -1;
for(int i = 0; i < n; i++)
if(col[i] == -1)
{
dfs(i, currentCol, dist);
currentCol = 1 - currentCol;
}
List<Integer> part0 = new ArrayList<Integer>();
List<Integer> part1 = new ArrayList<Integer>();
if(bad)
return noSolution;
for(int i = 0; i < n; i++)
if(col[i] == 0)
part0.add(i);
else
part1.add(i);
if(part0.size() == 0 || part1.size() == 0)
return noSolution;
int[] ret = new int[(n-1)*2];
int p = 0;
for(int i = 0; i < part1.size(); i++)
{
ret[p] = part0.get(0);
p ++;
ret[p] = part1.get(i);
p ++;
}
for(int i = 1; i < part0.size(); i++)
{
ret[p] = part0.get(i);
p ++;
ret[p] = part1.get(0);
p ++;
}
return ret;
}
}
aW1wb3J0IGphdmEudXRpbC5BcnJheUxpc3Q7CmltcG9ydCBqYXZhLnV0aWwuTGlzdDsKCnB1YmxpYyBjbGFzcyBPZGRFdmVuVHJlZUhhcmQgewoKICAgIGludFtdIGNvbDsKICAgIGJvb2xlYW4gYmFkOwoKICAgIHZvaWQgZGZzKGludCBjdXIsIGludCB0bywgU3RyaW5nW10gZGlzdCkKICAgIHsKICAgICAgICBpZihjb2xbY3VyXSA9PSAtMSkKICAgICAgICB7CiAgICAgICAgICAgIGNvbFtjdXJdID0gdG87CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIGlmKGNvbFtjdXJdICE9IHRvKSB7CiAgICAgICAgICAgICAgICBiYWQgPSB0cnVlOwogICAgICAgICAgICB9CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICAgICAgZm9yKGludCBpID0gMDsgaSA8IGRpc3QubGVuZ3RoOyBpKyspCiAgICAgICAgewogICAgICAgICAgICBpZihkaXN0W2N1cl0uY2hhckF0KGkpID09ICdFJyB8fCBkaXN0W2ldLmNoYXJBdChjdXIpID09ICdFJykKICAgICAgICAgICAgICAgIGRmcyhpLCB0bywgZGlzdCk7CiAgICAgICAgICAgIGlmKGRpc3RbY3VyXS5jaGFyQXQoaSkgPT0gJ08nIHx8IGRpc3RbaV0uY2hhckF0KGN1cikgPT0gJ08nKQogICAgICAgICAgICAgICAgZGZzKGksIDEtdG8sIGRpc3QpOwogICAgICAgIH0KICAgIH0KCiAgICBwdWJsaWMgaW50W10gZ2V0VHJlZShTdHJpbmdbXSBkaXN0KQogICAgewogICAgICAgIGludFtdIG5vU29sdXRpb24gPSBuZXcgaW50WzFdOwogICAgICAgIG5vU29sdXRpb25bMF0gPSAtMTsKCiAgICAgICAgaW50IG4gPSBkaXN0Lmxlbmd0aDsKICAgICAgICBjb2wgPSBuZXcgaW50W25dOwogICAgICAgIGJhZCA9IGZhbHNlOwoKICAgICAgICBpbnQgY3VycmVudENvbCA9IDA7CiAgICAgICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgICAgICAgICAgY29sW2ldID0gLTE7CiAgICAgICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgICAgICAgICAgaWYoY29sW2ldID09IC0xKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBkZnMoaSwgY3VycmVudENvbCwgZGlzdCk7CiAgICAgICAgICAgICAgICBjdXJyZW50Q29sID0gMSAtIGN1cnJlbnRDb2w7CiAgICAgICAgICAgIH0KCiAgICAgICAgTGlzdDxJbnRlZ2VyPiBwYXJ0MCA9IG5ldyBBcnJheUxpc3Q8SW50ZWdlcj4oKTsKICAgICAgICBMaXN0PEludGVnZXI+IHBhcnQxID0gbmV3IEFycmF5TGlzdDxJbnRlZ2VyPigpOwogICAgICAgIGlmKGJhZCkKICAgICAgICAgICAgcmV0dXJuIG5vU29sdXRpb247CiAgICAgICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgICAgICAgICAgaWYoY29sW2ldID09IDApCiAgICAgICAgICAgICAgICBwYXJ0MC5hZGQoaSk7CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgIHBhcnQxLmFkZChpKTsKCiAgICAgICAgaWYocGFydDAuc2l6ZSgpID09IDAgfHwgcGFydDEuc2l6ZSgpID09IDApCiAgICAgICAgICAgIHJldHVybiBub1NvbHV0aW9uOwoKICAgICAgICBpbnRbXSByZXQgPSBuZXcgaW50WyhuLTEpKjJdOwogICAgICAgIGludCBwID0gMDsKICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDwgcGFydDEuc2l6ZSgpOyBpKyspCiAgICAgICAgewogICAgICAgICAgICByZXRbcF0gPSBwYXJ0MC5nZXQoMCk7CiAgICAgICAgICAgIHAgKys7CiAgICAgICAgICAgIHJldFtwXSA9IHBhcnQxLmdldChpKTsKICAgICAgICAgICAgcCArKzsKICAgICAgICB9CiAgICAgICAgZm9yKGludCBpID0gMTsgaSA8IHBhcnQwLnNpemUoKTsgaSsrKQogICAgICAgIHsKICAgICAgICAgICAgcmV0W3BdID0gcGFydDAuZ2V0KGkpOwogICAgICAgICAgICBwICsrOwogICAgICAgICAgICByZXRbcF0gPSBwYXJ0MS5nZXQoMCk7CiAgICAgICAgICAgIHAgKys7CiAgICAgICAgfQogICAgICAgIHJldHVybiByZXQ7CiAgICB9Cn0K