P6722 「MCOI-01」Village 村庄

今天，珂爱善良的0x3喵酱骑着一匹小马来到了一个村庄。 “诶，这个村庄的布局 ……” “好像之前我玩 Ciste 的地方啊 qwq” 0x3喵酱有一个地图，地图有着这个村庄的信息。 然后0x3喵酱要通过这张地图来判断 Ciste 有解无解啦 ~ 注：Ciste 是《请问您今天要来点兔子吗》中的一种藏宝图游戏

村庄被简化为一个 $n$ 个节点（编号为 $1$ 到 $n$）和 $n-1$ 条边构成的无向连通图。 0x3喵酱认为这个无向图里的信息跟满足以下条件的新图有关： - 新图的点集与原图相同 - 在新图中 $u,v$ 之间有无向边 是 在原图中 $dis(u,v) \ge k$ 的**充分必要条件** （$k$ 为给定常量，$dis(u,v)$ 表示编号为 $u$ 的点到编号为 $v$ 的点最短路的长度） 0x3喵酱还认为这个"新图"如果为二分图，则 Ciste "有解"，如果"新图"不是二分图这个 Ciste "无解"。（如果您不知道二分图请翻到提示） 那么0x3喵酱想请您判断一下这个 Ciste 是否"有解"。

无

无

#### 样例解析 对于样例中的 **第一组** 数据： 原图：  新图：  新图不为二分图，故输出 `Baka Chino`。 对于 **第三组** 数据： 原图：  新图：  新图为二分图，故输出 `Yes`。 #### 数据规模与约定 **本题采用捆绑测试**。 - Subtask 1（16 pts）$\ $ ：$n \le 10$。 - Subtask 2（24 pts）$\ $ ：$n \le 100$。 - Subtask 3（8 pts）$\ $ ：$n \le 1000$。 - Subtask 4（28 pts）：图退化成一条链。 - Subtask 5（24 pts）：无特殊限制。 对于 $100\%$ 的数据，$n \le 10^5$，$T \le 10$，$v \le 1000$，$k \le 1000000$。 本题数据使用 [CYaRon](https://www.luogu.org/discuss/show?postid=11410) 生成。 #### 提示 **二分图** 又称作二部图，是图论中的一种特殊模型。设 $G=(V,E)$ 是一个无向图，如果顶点 $V$ 可分割为两个互不相交的子集 $(A,B)$，并且图中的每条边 $(i,j)$ 所关联的两个顶点 $i$ 和 $j$ 分别属于这两个不同的顶点集 $(i \in A,j \in B)$，则称图 $G$ 为一个二分图。（摘自[百度百科](https://baike.baidu.com/item/%E4%BA%8C%E5%88%86%E5%9B%BE/9089095?fr=aladdin)） #### 说明 Minecraft OI Round 1 A - Idea：0x3喵酱 - Solution/Std：0x3喵酱 - Data：0x3喵酱 - Tester：tarjin