시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 256 MB | 148 | 34 | 14 | 17.722% |
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.
In the first line of the standard input, there are two integers, n and k (1 ≤ n ≤ 60, 0 ≤ k ≤ 1,000,000, k ≤ 2^n-1, n⋅k ≤ 5,000,000), 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 n 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 n characters 0 and/or 1. 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
2 2 00 11 01 10
NIE
The following are two examples of a walk from 0000 to 1011: