랜덤 워크

동전 던지는 원숭이 군단(Army of Coin-tossing Monkeys, ACM)은 무작위성을 만들어 파는 일을 한다. 좋은 난수는 암호학, 온라인 도박, 무작위 알고리즘, 그리고 프로그래밍 대회가 끝나기 직전의 절박한 시도 등 여러 분야에서 중요하다.

최근 가장 뛰어난 원숭이 한 마리가 은퇴했는데, 떠나기 전에 동전 던지기 결과를 직접 쓰는 것보다 더 값싸게 무작위성을 만드는 방법을 고안했다. 이 방법은 $0, 1, \ldots, 2^n - 1$ 로 번호가 매겨진 $2^n$ 개의 정점을 가진 무방향 그래프에서 시작한다. $k$ 개의 무작위 $n$-비트 수를 만들기 위해, 원숭이들은 동전 $n$ 개를 던져 시작 정점을 고르고, 그 정점의 번호를 첫 번째 출력으로 삼는다. 그다음에는 현재 정점에 연결된 간선 중 하나를 균등하게 무작위로 골라 그 간선을 따라 이웃 정점으로 이동하고, 도착한 정점의 번호를 다음 출력으로 삼는다. 이어서 다시 현재 정점에 연결된 간선 하나를 균등하게 무작위로 골라(방금 지나온 간선을 다시 고를 수도 있다) 이동하며, 도착한 정점을 출력한다. 이 과정을 $k$ 개의 수가 출력될 때까지 반복한다.

그래프마다 출력 분포가 다르며, 어떤 것은 그다지 무작위적이지 않다. ACM은 $k$ 개의 출력 수 각각의 $n$ 개 비트 모두에 대해, 그 비트가 $1$ 일 확률이 $25%$ 보다 엄격히 크고 $75%$ 보다 엄격히 작을 때 그 그래프를 좋은(good) 그래프로 본다. 주어진 그래프가 좋은 그래프인지 판정하여라.

입력은 여러 개의 데이터 집합으로 이루어진다. 각 데이터 집합은 공백으로 구분된 세 정수 $k$, $n$, $e$ 로 시작하는 줄로 시작한다. 여기서 $k$ 는 생성할 $n$-비트 수의 개수, $e$ 는 간선의 개수이며 $1 \le k \le 100$, $1 \le n \le 10$, $1 \le e \le 2000$ 이다. 이어지는 $e$ 개의 줄에는 각각 공백으로 구분된 두 정수 $v_1$, $v_2$ 가 주어지며 $0 \le v_1, v_2 < 2^n$, $v_1 \ne v_2$ 이고, 이는 하나의 무방향 간선을 뜻한다. 모든 정점은 적어도 하나의 간선을 가짐이 보장되며, 같은 정점 쌍 사이에 여러 개의 간선이 있을 수도 있다.

마지막 데이터 집합 뒤에는 $k = n = e = 0$ 인 줄이 오며, 이 줄은 처리하지 않는다.

각 데이터 집합에 대해, 그래프가 좋으면 Yes 를, 그렇지 않으면 No 를 한 줄에 출력한다.