這個題目來自於：https://tnjbox.github.io/blockly-lab/?course=114TCPJ14&task=114TCPJ14-6
這是*科技創意實作競賽-資訊科技組(簡稱資科競賽)*再做的，不過也可以用Py解
過年大考驗————親等計算機(難)
【題目說明】
過年回老家，最難的就是分清楚親戚關係。我們定義「親等」為兩個人之間到「最近共同祖先」的距離總和。
【規則說明】
- 距離計算：你與父母距離為1，與祖父母距離為2。依此類推(自己與自己的距離為0)。
- 親等公式：親等=(X往上到共同祖先的步數)+(Y往上到共同祖先的步數)。
- 唯一性：若有多位共同祖先，以親等最小(路徑最近)的為準。
- 無關係：若兩人在名單中完全沒有共同祖先，輸出不是親戚。
【輸入格式】
- 第一個輸入：一個整數N，代表親戚關係的數量。
- 第二個輸入：N個父親代號(大寫字母)。
- 第三個輸入：N個兒子代號(與父親代號對應)。
- 第四個輸入：兩個欲查詢親等關係的代號X與Y。
【輸出格式】
輸出一個整數代表親等值；若無共同祖先則輸出不是親戚。
範例
範例輸入1
3
AAB
BCD
CD範例輸出1
3C的父親是A(1步)； D的父親是B，B的父親是A(2步)。 最近共同祖先為A，親等 = 1 + 2 = 3
範例輸入2
2
EF
GH
EF範例輸出2
不是親戚E與F分屬不同家族血緣，完全沒有共同祖先，故輸出不是親戚
測資
接下來是測試用測資，我用AI做的：
一、直系血親
- 父子
1
A
B
AB輸出：
1（共同祖先取 A 自己：0 + 1）
- 祖孫（2 親等）
2
AB
BC
AC輸出：
2- 反向查詢（孫在前、祖在後，順序不影響答案）
2
AB
BC
CA輸出：
2- 深族譜（7 親等）
7
ABCDEFG
BCDEFGH
AH輸出：
7（A→B→…→H 一條長鏈）
- 查詢自己
3
AAB
BCD
CC輸出：
0二、旁系血親
- 兄弟姊妹（2 親等）
2
AA
BC
BC輸出：
2（1 + 1）
- 叔姪（3 親等，同題目範例1）
3
AAB
BCD
CD輸出：
3- 堂兄弟（4 親等）
4
AABC
BCDE
DE輸出：
4（D、E 到共同祖先 A 各 2 步）
三、特殊情況
- 多位共同祖先，取最小（規則3）
5
ZAABC
ABCDE
DE輸出：
4 （共同祖先有 A：2+2=4 和 Z：3+3=6，取最小）
- 查詢的人物完全不在名單中
2
AA
BC
BD輸出：
不是親戚（D 沒出現在任何關係裡）
- 兩個不同家族（同題目範例2）
2
EF
GH
EF輸出：
不是親戚- 極端邊界 N=0（若測資可能出現）
0
AB輸出：
不是親戚（第二、三行為空行）
四、同一棵族譜、不同查詢（前三行固定，一次測多種形式）
6 ZZAABC ABCDEF 配合不同的第四行：
查詢行 輸出 CD 2 DF 3 FE 5 FZ 3
五、模糊邊界（題目未定義，僅供參考）
- 同一個兒子有兩個父親（非樹狀）
2
AB
CC
AB輸出：
不是親戚按題目定義（A、B 無共同祖先）
py解
from collections import deque
n = int(input())
f = list(input())
son = list(input())
pa = input()
x, y = pa[0], pa[1]
d = {}
for f, s in zip(f, son):
d.setdefault(s, []).append(f)
def ans_(start):
c = {start: 0}
q = deque([start])
while q:
temp = q.popleft()
for p in d.get(temp, []):
if p not in c:
c[p] = c[temp] + 1
q.append(p)
return c
dr,dc = ans_(x),ans_(y)
c = dr.keys() & dc.keys()
print(min(dr[a]+dc[a] for a in c) if c else "不是親戚")