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