本题没有可用的提交语言。

题目描述

一群草药师决定搬到一个位于巨大森林边缘的新村庄。

村庄中房屋和道路的布局成为了一个主要问题：许多草药师是朋友，他们希望能够经常互相拜访，因此他们希望在房屋之间修建道路。然而，草药师们也以与其他所有人争吵而闻名。为了避免与他们不喜欢的人相遇，要求任何两条道路不能相交——村庄中不能有十字路口（当然也不能有其他形式的交叉；天桥会破坏景观，地下通道会破坏珍贵草药的根系）。此外，每位草药师还希望能够在不穿越任何道路的情况下到达森林（即“无限远”），也就是说，必须能够从每座房屋出发，在不穿越任何道路的情况下到达“无限远”。

你将获得草药师之间关系的描述。你的任务是判断是否可以建造这样一个理想的村庄。

输入格式

输入包含多个测试用例。

每个测试用例的第一行包含两个整数 $1 ≤ H ≤ 10,000$ 和 $0 ≤ F ≤ 20,000$，用一个空格分隔。$H$是草药师的数量，草药师的编号为 $0$ 到 $H-1$。$F$ 是朋友的对数。接下来的 $F$ 行描述朋友对。每行包含两个整数 $0 ≤ h1, h2 < H$，用一个空格分隔，表示编号为 $h1$ 和 $h2$ 的草药师是朋友。每对朋友只被描述一次。

测试用例之间没有分隔符。输入以一行两个 $0$ 结束。

输出格式

输出包含多行。输出的第 i 行对应于第 i 个测试用例。如果可以为对应的输入建造村庄，则输出 "Yes, village can be built"。如果不能建造这样的村庄，则输出 "No, village cannot be built"。

示例输入 1

3 3
0 1
0 2
1 2
4 6
0 1
0 2
0 3
1 2
1 3
2 3
0 0

示例输出 1

Yes, village can be built
No, village cannot be built

题目来源

CTU Open 2004