Random Walking

The Army of Coin-tossing Monkeys (ACM) is in the business of producing randomness. Good random numbers matter for many applications: cryptography, online gambling, randomized algorithms, and last-second panic attempts at solutions during programming contests.

One of the best monkeys recently retired, but before leaving invented a cheaper way to generate randomness than reading coin tosses directly. The method starts from an undirected graph with $2^n$ nodes labelled $0, 1, \ldots, 2^n - 1$. To generate $k$ random $n$-bit numbers, the monkeys toss $n$ coins to choose a starting node, and that node's number is the first output. They then pick a uniformly random edge incident to the current node and jump along it to the neighbouring node, whose number is the next output. From there they again pick a uniformly random incident edge (possibly the very edge they just arrived on), move, and output the node they land on. The walk continues until $k$ numbers have been output.

Different graphs produce different output distributions, and some are not very random. The ACM considers a graph good if, for every one of the $n$ bits in every one of the $k$ output numbers, the probability that the bit equals $1$ is strictly greater than $25\%$ and strictly less than $75\%$. Given a graph, decide whether it is good.

The input contains several data sets. Each data set begins with a line of three space-separated integers $k$, $n$, $e$, where $k$ is the count of $n$-bit numbers to generate and $e$ is the number of edges, with $1 \le k \le 100$, $1 \le n \le 10$, and $1 \le e \le 2000$. Each of the next $e$ lines contains two space-separated integers $v_1$ and $v_2$ with $0 \le v_1, v_2 < 2^n$ and $v_1 \ne v_2$, describing an undirected edge. Every node is guaranteed to have at least one incident edge, and there may be multiple edges between the same pair of nodes.

The last data set is followed by a line with $k = n = e = 0$, which must not be processed.

For each data set, print a single line containing Yes if the graph is good, or No otherwise.