BZPRO

#3421. Poi2013 Walk

内存限制：256 MiB 时间限制：100 Sec
提交 提交记录 讨论

题目描述

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.

样例

样例输入


			
4 6

0000 1011

0110

0111

0011

1101

1010

1001

样例输出


			
TAK

数据范围与提示

BZPRO Powered by XZYQvQ.
Github Repository