树的重构

题目背景

我们知道一棵带权树中若干指定节点两两之间的距离，但原树本身已经丢失。原树中可能还存在一些没有出现在距离矩阵中的辅助节点。你的任务是判断这些距离能否来自某棵边权均为正整数的树；若可以，还要找出所需节点总数最少的那棵树。

题目描述

一棵树是一个连通且无环的图。树的每条边都有一个正整数长度。

从某棵树中选出 $N$ 个节点，并计算这些节点两两之间在原树中的最短路长度，可以得到一个 $N\times N$ 的对称距离矩阵。

现在给定两个由十六进制数字组成的 $N\times N$ 字符矩阵 g1 和 g2。对于任意 $0\le i,j<N$，节点 $i$ 与节点 $j$ 之间的距离为：

$$d_{i,j}=16\cdot \operatorname{hex}(g1_{i,j})+\operatorname{hex}(g2_{i,j}),$$

其中 $\operatorname{hex}(c)$ 表示十六进制字符 $c$ 对应的数值，字符范围为 0 到 9 以及 A 到 F。

也就是说，g1[i][j] 是距离的十六进制高位，g2[i][j] 是低位。例如：

• g1[i][j] = '0'、g2[i][j] = 'A' 表示距离为 $10$；
• g1[i][j] = '2'、g2[i][j] = 'F' 表示距离为 $47$。

请判断是否存在一棵边长均为正整数的树，使给出的 $N$ 个节点两两之间的距离恰好等于上述矩阵。

原树可以包含不在这 $N$ 个给定节点之中的额外节点。若存在多种合法重构方案，请输出其中节点总数最少的方案所包含的节点数。显然，该节点数不会小于 $N$。

若不存在任何合法的树，输出 -1。

输入格式

第一行包含一个整数 $N$。

接下来 $N$ 行，每行包含一个长度为 $N$ 的字符串，依次表示矩阵 g1 的各行。

随后 $N$ 行，每行包含一个长度为 $N$ 的字符串，依次表示矩阵 g2 的各行。

输出格式

输出一个整数：

• 若可以重构出合法的树，输出所有合法重构方案中最少的节点总数；
• 若无法重构，输出 -1。

样例 1

输入

4
0000
0000
0000
0000
0444
4044
4404
4440

输出

5

说明

原树可以是一棵星形树：有一个中心节点，并有 $4$ 个给定节点分别通过一条长度为 $2$ 的边与中心相连。因此总节点数为 $5$。

样例 2

输入

4
0000
0000
0000
0000
0233
2033
3302
3320

输出

6

样例 3

输入

5
00001
00001
00011
00100
11100
066C6
60CA4
6C02C
CA20A
64CA0

输出

6

样例 4

输入

5
00000
00000
00001
00000
00100
06839
60E7B
8E0B1
37B0A
9B1A0

输出

7

数据范围

• $2\le N\le 50$；
• g1 和 g2 均恰好包含 $N$ 行，每行恰好包含 $N$ 个十六进制字符；
• 每个字符均为 0 到 9 或 A 到 F；
• g1 和 g2 的主对角线字符均为 0；
• g1 和 g2 均为对称矩阵；
• 任意两个不同节点之间的距离均为正数。