#P3552. [POI 2013] SPA-Walk

[POI 2013] SPA-Walk

Description

The names of towns in Byteotia are unique sequences of exactly nn bits. There are 2nk2^n-k towns in Byteotia, and thus, only kk sequences of nn 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 xx to the town yy, taking the existing roads. Your task is to determine whether such a walk is possible.

Input Format

The first line contains two integers nn and kk (1n601 \le n \le 60, 0k1 000 0000 \le k \le 1\ 000\ 000, k2n1k \le 2^n - 1, n×k5 000 000n \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 nn-bit sequences that do not correspond to any town, respectively.

The second line contains two strings, separated by a single space, each consisting of nn characters 0 and/or 1. These are the names of the towns xx and yy.

Each of the next kk lines contains one sequence of nn bits that does not correspond to any town. You may assume that xx and yy are not among these kk sequences.

Output Format

Print TAK if it is possible to walk from xx to yy, and NIE otherwise.

4 6
0000 1011
0110
0111
0011
1101
1010
1001

TAK

Hint

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

Translated by ChatGPT 5