首先路径不要求是简单的所以可以通过反复走一条边使得路径长度 +2。存在长度为 x 的路径意味着一定存在长度为 x+2 的路径，所以我们只关心一个点的奇最短路和偶最短路。
如果原图是一个二分图，那么每个点要么只存在奇路径要么只存在偶路径，所以只关心最短路。按照 dis
i
分层后，每个点连接到上一层即可，答案为 n−1。
接下来只考虑原图不是二分图的情况：令到该点的最短路长度为 x
i
，与最短路径奇偶不同的最短路长度为 y
i
，我们需要使得新图所有 (x
i
,y
i
) 和原图相同。
首先有一条边连接的 (x
u
,y
u
),(x
v
,y
v
) 一定有 ∣x
u
−x
v
∣≤1,∣y
u
−y
v
∣≤1，否则可以用较小者去更新较大者。
所以一个点 (x,y) 只可能和 (x±1,y±1) 连边（当然 x=y−1 时 (x+1,y−1) 为 (x,y) 自己）。
考察一组 (x,y) 的由来，由最短路的构成，一定满足以下两种情况之一：
从 (x−1,y−1) 转移来。
从 (x−1,y+1) 得到 x，从 (x+1,y−1) 得到 y（当 x=y−1 时 (x+1,y−1) 为 (x,y) 自己）。
(x+1,y+1) 可连可不连（对于这个点来说）。
特殊情况是 x=0 即 1 号点不需要向 (x−1,y+1) 连边。
然后接下来的思路很妙：考虑前面二分图按照 dis 分层，而现在难以按照 dis 分层了，分层的目的是为了将原图分成若干个相对较为独立的部分，现在考虑按照 x+y 分层，于是现在只需要考虑每层向上一层连当边和向这一层的左右连的边。
称 (x−1,y−1) 为 (x,y) 的“上面”，(x−1,y+1) 为“左边”，(x+1,y−1) 为“右边”，每个点要么连上面，要么同时连左右（右可能是自环）。
接下来考虑一层一层做。
考虑每层的样子一定形如有若干段，如果不是末尾可以连接自环的段的话一定两个端点都可以向上连。如果末尾可以连接自环那么末尾可能不能向上。（因为这些 (x,y) 是由原图求出来的，所以一定存在一种合法的构造，不会存在一个点上面左右都不能连接）
代码：
