福利

Ready to put your newfound language skills into use? Get 40% off CodeCrafter's real-world proficiency projects!

领取你的折扣

轨道

MoonScript

练习

相对距离

中等

简介

你受聘开发Noble Knots，专为贵族打造的最热门新交友应用！经过几个世纪的王室通婚，事情变得……_复杂_了。为了避免出现_哎呀，我们是双胞胎_这样的情况，你的任务是构建一个系统，用来检查两个人的血缘有多近。

Noble Knots 的灵感来自冰岛的“Islendinga-App”，它背后有一个数据库，记录了自冰岛定居以来冰岛人之间所有已知的亲缘关系。你的算法将判断王室家谱中两个人之间的亲疏程度。

你的应用能促成一段完美的姻缘吗？

说明

你的任务是确定家谱中两个人之间的分隔度。这类似于流行文化中的那个说法：每位好莱坞演员都与 Kevin Bacon 相隔不超过六度。

输入中会给出所有父母的名字以及他们的子女。
每个名字都是唯一的，一个孩子_可以_有一位或两位父母。
分隔度定义为一个人到另一个人之间的最短连接数。
如果两个人之间没有连接，就返回一个表示“no known relationship.”的值。具体实现请参见测试用例。

示例

给定下面这棵家谱树：

      ┌──────────┐            ┌──────────┐     ┌───────────┐
      │  Helena  │            │  Erdős   ├─────┤  Shusaku  │
      └───┬───┬──┘            └─────┬────┘     └────┬──────┘
      ┌───┘   └───────┐             └───────┬───────┘
┌─────┴────┐     ┌────┴───┐           ┌─────┴────┐
│   Isla   ├─────┤ Tariq  │           │   Kevin  │
└────┬─────┘     └────┬───┘           └──────────┘
     │                │
┌────┴────┐      ┌────┴───┐
│   Uma   │      │ Morphy │
└─────────┘      └────────┘

Tariq 和 Uma 之间的分隔度是 2（Tariq → Isla → Uma）。 Isla 和 Kevin 之间没有已知关系，因为给定数据中两者没有连接。 Uma 和 Isla 之间的分隔度是 1。

Note

Isla 和 Tariq 是兄弟姐妹，他们的分隔度是 1。同样，按照这个实现，你和你父亲的兄弟之间的分隔度会是 2。