On a Saturday morning, $n$ boys will gather on the "Bajtusie" Sports Club field. Fortunately, the number of boys is even. This allows all the boys to spend their Saturday happily playing soccer.

Bajtazar is the club's coach, and he is responsible for selecting the lineups for the individual matches. Bajtazar knows that the boys love to compete, so he decided to arrange the team lineups in such a way that every two boys have a chance to play against each other in some match (i.e., to play on opposing teams at least once).

Taking the boys' skills into account, Bajtazar has already proposed the team lineups for the next $m$ matches. In each match, all the boys will play, divided into two teams of $n/2$ players each. Help Bajtazar determine whether every pair of boys will play against each other in at least one of the scheduled matches.

Input

The first line of input contains two integers $n$ and $m$ ($4 \le n \le 40\,000$, $1 \le m \le 50$), representing the number of boys and the number of scheduled matches. Each boy has a number written on his jersey—an integer between 1 and $n$. The numbers on the boys' jerseys are pairwise distinct.

Each of the next $m$ lines contains $n$ pairwise distinct integers in the range from 1 to $n$ describing the team lineups for the individual matches. The first $n/2$ numbers in each line are the numbers of the players on the first team, and the second $n/2$ numbers are the numbers of the players on the second team.

Output

Your program should output a single word TAK (YES) or NIE (NO), depending on whether every pair of boys will play against each other in at least one match or not.

Examples

Input 1

6 3
4 6 1 3 5 2
1 4 5 2 3 6
1 2 6 4 5 3

Output 1

TAK

Input 2

6 3
4 6 1 3 5 2
1 4 5 2 3 6
1 2 3 4 5 6

Output 2

NIE

Note

In the first example, every pair of players plays on opposing teams in one match (e.g., players numbered 1 and 6), in two matches (e.g., players 1 and 2), or even in all three matches (e.g., players 1 and 3). In the second example, players numbered 2 and 3 always play on the same team.