P3552 [POI 2013] SPA-Walk

The names of towns in Byteotia are unique sequences of exactly $n$ bits. There are $2^n-k$ towns in Byteotia, and thus, only $k$ sequences of $n$ bits do not correspond to any town. Some pairs of towns are connected by roads. Specifically, two towns are directly linked by a road if and only if their names differ in exactly one bit. The roads do not cross outside of towns. Byteasar intends to take a stroll — he plans to walk from the town $x$ to the town $y$, taking the existing roads. Your task is to determine whether such a walk is possible.

The first line contains two integers $n$ and $k$ ($1 \le n \le 60$, $0 \le k \le 1\ 000\ 000$, $k \le 2^n - 1$, $n \times k \le 5\ 000\ 000$), separated by a single space. These are the length of the town names in bits and the number of $n$-bit sequences that do not correspond to any town, respectively. The second line contains two strings, separated by a single space, each consisting of $n$ characters 0 and/or 1. These are the names of the towns $x$ and $y$. Each of the next $k$ lines contains one sequence of $n$ bits that does not correspond to any town. You may assume that $x$ and $y$ are not among these $k$ sequences.

Print TAK if it is possible to walk from $x$ to $y$, and NIE otherwise.

There are $2^n$ binary strings of length $n$. Two strings are connected by an edge if and only if they differ in exactly one bit. After removing $k$ of these $2^n$ strings, determine whether the two specified strings are reachable from each other. Translated by ChatGPT 5