약초학자들의 마을

약초학자들이 거대한 숲의 경계에 새 마을을 세우기로 했다.

문제는 집과 길을 어떻게 배치하느냐이다. 약초학자들 중 상당수는 서로 친구여서 자주 오가고 싶어 하므로, 친구인 두 사람의 집 사이에는 길을 놓으려 한다. 하지만 약초학자들은 친구가 아닌 사람과는 다투기로 유명하다. 싫어하는 사람과 마주칠 일을 없애기 위해, 어떤 두 길도 서로 교차해서는 안 된다. 즉 마을 안에 교차로가 있어서는 안 되며, 길들은 오직 끝점(집)에서만 만날 수 있다. 입체 교차도 허용되지 않는다. 고가도로는 경관을 해치고, 지하도는 귀한 약초의 뿌리를 망가뜨리기 때문이다.

또한 각 약초학자는 어떤 길도 건너지 않고 숲으로 나갈 수 있어야 한다. 다시 말해, 모든 집에서 길을 건너지 않고 바깥의 '무한히 먼 곳'까지 갈 수 있어야 한다.

약초학자들 사이의 친구 관계가 주어질 때, 이런 이상적인 마을을 지을 수 있는지 판정하여라.

입력은 여러 개의 테스트로 이루어진다.

각 테스트의 첫째 줄에는 두 정수 $H$와 $F$가 공백 하나로 구분되어 주어진다 ($1 \le H \le 10\,000$, $F \ge 0$). $H$는 약초학자의 수이며, 각 약초학자는 $0$부터 $H-1$까지의 정수 번호를 가진다. $F$는 친구 쌍의 개수이다.

이어지는 $F$개의 줄에 각 친구 쌍이 주어진다. 각 줄에는 두 정수 $h_1$, $h_2$가 공백 하나로 구분되어 주어지며 ($0 \le h_1, h_2 < H$), 번호가 $h_1$인 약초학자와 $h_2$인 약초학자가 친구임을 뜻한다. 같은 친구 쌍은 정확히 한 번만 주어진다.

여러 테스트는 구분자 없이 곧바로 이어진다. 입력의 끝은 두 개의 $0$이 적힌 줄로 표시된다.

각 테스트마다 한 줄씩 출력한다. $i$번째 줄은 $i$번째 테스트에 대한 답이다. 해당 테스트에서 마을을 지을 수 있으면 그 줄에 Yes, village can be built 를, 지을 수 없으면 No, village cannot be built 를 출력한다.