题目描述

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 with roads. Specifically, two towns are directly linked by a road if and only if their names differ in a single bit. The roads do not cross outside of towns. Byteasar intends to take a stroll - he intends to walk from the town x  to the town y , taking the existing roads. Your task is to write a program that will determine if such a walk is possible. 有2^N-k个点，每个点有一个独一无二的、长度为n的01串，但是有k个01串没有出现过。每两个点之间有连边当且仅当两个01串之间有且仅有一个位置是不同的。现在询问x和y两个字符串能不能互相到达

输入格式

**In the first line of the standard input, there are two integers, N  and K (1<=N<=60,0<=K<=1000000,k<=2^N-1, N*k<=5000000)  separated by a single space. These are the length of town names in bits and the the number of N -bit sequences that do not correspond to any town, respectively. In the second line, there are two strings, separated by a single space, each consisting of   characters 0 and/or 1. These are the names of the towns x and y. In the K lines that follow, all the sequences of N bits that do not correspond to any town are given, one sequence per line. Each such sequence is a string of   characters 0 and/or1. You may assume that x  and  y  are not among those K sequences. **

输出格式

**Your program should print to the standard output the word TAK (Polish for yes) if walking from the town x to the town y  is possible, and the word NIE (Polish for no) otherwise. **

0000 1011
0110
0111
0011
1101
1010
1001

提示

没有写明提示

题目来源

鸣谢HJWJBSR提供译文