CF690F3.Tree of Life (hard)

To add insult to injury, the zombies have taken all but two drawings from Heidi! Please help her recover the Tree of Life from only these two drawings.

雪上加霜的是，僵尸们拿走了海蒂所有的画作，仅剩下两幅！请仅凭这两幅画帮助她复原“生命之树”。

The input format is the same as in the medium version, except that now the bound on n is 2 ≤ n ≤ 1000 and that k = 2.

输入格式与中等难度版本相同，只是此时对 $n$ 的约束变为 $2 \leq n \leq 1000$，且 $k = 2$。

The same as in the medium version.

与中等难度版本相同。