・あるノードからの距離が奇数同士のノード間距離は偶数

上記で？が存在する場合は、一つをOにして、？がなくなるまでDFSで判定していく。

最後にすべての状態がわかるので、そこからひとつのエッジ集合を返してあげればよい。

int d[60],n;
vector<string> x;

class OddEvenTreeHard {

public:

bool dfs(){
FORE(i,0,n)FORE(j,0,n){
int update=0;
if(x[i][j]=='?'){
if(d[i]!=-1 && d[j]!=-1){
x[i][j]= (d[i]^d[j]) ? 'O' : 'E';
x[j][i]=x[i][j];
update=1;
}
}
else{
int cur= x[i][j]=='O' ? 1 : 0;
if(d[i]!=-1 && d[j]!=-1){
if(cur!=(d[i]^d[j]))return false;
}
else if(d[i]!=-1 && d[j]==-1)d[j]=(cur^d[i]),update=1;
else if(d[i]==-1 && d[j]!=-1)d[i]=(cur^d[j]),update=1;
}
if(update)dfs();
}
return true;
}

vector<int> getTree(vector<string> x_) {
x=x_;
n=x.size();

memset(d,-1,sizeof(d));
vector<int> invalid;
invalid.push_back(-1);

FORE(i,0,n){
if(x[i][i]=='O')return invalid;
x[i][i]='E';
}
FORE(i,0,n)FORE(j,0,n){
if(x[i][j]!='?' && x[j][i]!='?' && x[i][j]!=x[j][i])return invalid;
if(x[i][j]=='?')x[i][j]=x[j][i];
else x[j][i]=x[i][j];
}

FORE(i,0,n){
if(x[0][i]=='O')d[i]=1;
else if(x[0][i]=='E')d[i]=0;
}

if(dfs()==false)return invalid;

while(1){
int finish=1;
FORE(i,0,n)FORE(j,0,n)if(x[i][j]=='?')finish=0;
if(finish)break;

FORE(i,0,n)if(x[0][i]=='?'){
x[0][i]='O',x[i][0]='O';
d[i]=1;
break;
}
if(dfs()==false)return invalid;
}

int r0=0,r1=-1;
FORE(i,0,n)if(x[0][i]=='O')r1=i;
if(r1==-1)return invalid;

vector<int> ans;
ans.push_back(r0),ans.push_back(r1);
FORE(i,1,n)if(i!=r1){
if(d[i]){
ans.push_back(r0),ans.push_back(i);
}else{
ans.push_back(i),ans.push_back(r1);
}
}

return ans;
}

};