　$36$ 個の実数 $(s_1,s_2, \ldots,s_{36})$ を変数とする以下の連立方程式を $P$ とよぶ．
$$ s_{b_1}+s_{c_1}=1, \quad s_{b_2}+s_{c_2}=2 ,\quad \ldots,\quad s_{b_{35}}+s_{c_{35}}=35  $$
一般論として，連立 $n$ 元一次方程式の解が一意に定まるには，少なくとも $n$ 本の式が必要である．したがって，$P$ に式を $1$ 本加えることで唯一解が生まれることから，$P$ の中に過剰な式，あるいは矛盾した式は存在してはならない．\
　$1,2,\ldots, 36$ を頂点とし，$b_i,c_i$ の間に辺を張った無向グラフ $Q$ を考える．頂点 $x$ を含む連結成分が木であるとき，$s_x$ の値をどのように定めても，辺に沿って残りの値を矛盾なく定めることが出来るため，$P$ において $s_x$ の値は一意に定まらない．いま，$Q$ は辺数が頂点数より少ないため，木の連結成分が存在することに注意する．\
　ここで，木の連結成分が $2$ つ以上存在したとき，$Q$ にどのように辺を $1$ 本追加しても，木の連結成分が $1$ つ以上存在したままになる．これは，$P$ に $s_x-s_y=z$ の形式の式をどのように追加しても，唯一解になり得ないことを意味する．したがって，$Q$ は連結成分のうち，木をちょうど $1$ つもつ（以下，単に**木**といえばこの連結成分をさす）．また，木でない連結成分は，それぞれ辺と頂点の数が同じでなければならないから，すべて閉路である．\
　ある閉路の長さが偶数 $2n$ のとき，含まれる頂点を順に $q_1, q_2 ,\ldots,  q_{2n}$ とすると，
$$
(s_{q_1}+s_{q_2})-(s_{q_2}+s_{q_3})+(s_{q_3}+s_{q_4})\cdots +(s_{q_{2n-1}}+s_{q_{2n}})=s_{q_1}+s_{q_{2n}}
$$
から，$P$ において $s_{q_1}+s_{q_{2n}}=z$ は過剰または矛盾した式となる．すなわち，偶数長の閉路は存在しない．\
　逆に閉路の長さが奇数 $2n+1$ のとき，含まれる頂点を順に $q_1, q_2 ,\ldots,  q_{2n+1}$ とすると，
$$
(s_{q_1}+s_{q_2})-(s_{q_2}+s_{q_3})+(s_{q_3}+s_{q_4})\cdots -(s_{q_{2n}}+s_{q_{2n+1}})+(s_{q_{2n+1}}+s_{q_{1}})=2s_{q_1}
$$
などによって，$P$ において $s_{q_i}$ の値はすべて矛盾なく一意に定まる．よって,
$$M=36-(\text{木の頂点数})．$$
　さて，$P$ に $s_x+s_y=36$ を付け足したとき，$P$ が唯一解をもつような $(x,y)$ の条件について考える．$x,y$ のいずれかは木に含まれていなければならず，いずれか一方のみが木に含まれている場合は明らかに適する．\
　以下，$x,y$ がともに木に含まれている場合について考える．基本的には上と同様である．

- 頂点 $x,y$ の距離が偶数である場合 \
　$x,y$ 間のパスに含まれる頂点を順に $q_1(=x), q_2 ,\cdots  q_{2n+1}(=y)$ とすると，
$$
(s_{q_1}+s_{q_2})-(s_{q_2}+s_{q_3})+(s_{q_3}+s_{q_4})\cdots -(s_{q_{2n}}+s_{q_{2n+1}})=s_{q_1}-s_{q_{2n+1}}=s_x-s_y
$$
となり，$s_x-s_y=36$ は過剰または矛盾した式となるから不適．
- 頂点 $x,y$ の距離が奇数である場合 \
　$x,y$ 間のパスに含まれる頂点を順に $q_1(=x), q_2 ,\cdots  q_{2n}(=y)$ とすると，
$$
(s_{q_1}+s_{q_2})-(s_{q_2}+s_{q_3})+(s_{q_3}+s_{q_4})\cdots +(s_{q_{2n-1}}+s_{q_{2n}})+(s_{q_1}-s_{q_{2n}})=2s_{q_1}
$$
などによって，$P$ において $s_{q_i}$ の値はすべて矛盾なく一意に定まる．

　さて，これを踏まえて木の頂点を赤と青の二色で塗る．ここで，同じ色の頂点が辺で隣り合わないようにする．これは可能である（木は二部グラフである）．このとき，$2$ 頂点間の距離が偶数であることと，同色であることは同値である．赤，青で塗られた頂点の数をそれぞれ $V,W$ とすると，$(x,y)$ として**不適**な組は $M^2+V^2+W^2$ 個である．\
　逆に，$V,W\gt 0$ のとき，赤，青で塗られた頂点がそれぞれ $V,W$ 個の木が構築できる．よって，
$$M+V+W=36,\quad M^2+V^2+W^2=36^2-736=560$$
のとき $M$ としてあり得る値の $3$ 乗和を求めれば良く，これは $4^3 + 12^3 + 20^3 = \mathbf{9792}$ とわかる．
公式解説
https://onlinemathcontest.com/contests/omc180/editorial/4112
　 $1$ 以上 $36$ 以下の整数からなる数列 $b_1, b_2, \ldots, b_{35}$ と $c_1, c_2, \ldots, c_{35}$ は次の条件をみたします：
- $36$ 個の実数 $(a_1,a_2, \ldots,a_{36})$ を変数とする連立方程式
$$ a_{b_1}+a_{c_1}=1, \quad a_{b_2}+a_{c_2}=2 ,\quad \ldots,\quad a_{b_{35}}+a_{c_{35}}=35,\quad a_{x}-a_{y}=36  $$
が一意に解をもつような，$1$ 以上 $36$ 以下の整数の組 $(x,y)$ がちょうど $736$ 個存在する．

　いま，$36$ 個の実数 $(s_1,s_2, \ldots,s_{36})$ を変数とする連立方程式
$$ s_{b_1}+s_{c_1}=1, \quad s_{b_2}+s_{c_2}=2 ,\quad \ldots,\quad s_{b_{35}}+s_{c_{35}}=35  $$
において，$s_t$ の値が一意に定まるような $t$ $(1\leq t\leq36)$ はちょうど $M$ 個存在しました．$M$ としてありうる正整数値すべての $3$ 乗和を求めてください．