The Mahmut Traveling Agency has decided to give a discount on their ship tour to all who are called Şehmettin. After legally changing your name to Şehmettin you realized that the conditions for the trip are too complicated. You are not even sure if there is a combination of islands that you can choose.

There are \(\mathbf{2\times N}\) islands numbered from \(\mathbf{1}\) to \(\mathbf{2\times N}\).

According to The Mahmut Traveling Agency you must adhere to 2 types of conditions listed below:

• You must travel to exactly one island for any 2 islands numbered with N difference.(So if an island is numbered as \(\mathbf{A}\) its pair is either \(\mathbf{A+N}\) or \(\mathbf{A-N}\))
• You must travel to at least one of the 2 islands for every \(\mathbf{K}\) island pairs set by the traveling agency
  • This group of rules can include identical pairs(e.g. [1,1] or [5,5])
  • This group of rules will not include the same pair twice or its swapped version (e.g. if [1,2] is a pair we will not have [2,1] or another [1,2])

Your job is to figure out if there is a possible combination of islands according to The Mahmut Traveling Agency's conditions.

Input

• The first line contains 2 integers:
  • \(1\leq\mathbf{N}\leq2\times10^3\) (\(\mathbf{N}\) = (The number of islands)/2)
  • \(1\leq\mathbf{K}\leq 2\mathbf{N} \times(2\mathbf{N}+1)/2\) (\(\mathbf{K}\) = Number of island pairs set by the agency)
• The \(\mathbf{K}\) consecutive lines contain \(\mathbf{2}\) integers each:
  • \(1\leq a,b\leq2\times \mathbf{N}\) (Island pairs set by the agency)

Output

If there is an island combination print T (as in True)

If there isn't print F (as in False)

Examples

Input 1:

4 3
1 2
2 3
3 4

Output 1:

T

Input 2:

4 5
5 2
6 3
7 4
7 8
3 1

Output 2:

F

Explanation:

Input 1:

• According to first group of rules we have to choose one island from every 4 pairs [1,5],[2,6],[3,7],[4,8]
• According to second group of rules we must choose exactly one island from these 3 pairs: [1,2],[2,3],[3,4]

Since [1,2,3,4] adheres every condition the result is True.

Input 2:

• According to the first group of rules we have to choose one island from every 4 pairs [1,5],[2,6],[3,7],[4,8]
• According to the second group of rules we must choose exactly one island from these 5 pairs: [5,2],[6,3],[7,4],[7,8],[3,1]

Because of the first rule, there are 16 different combinations we can try

• [1,2,3,4] does not adhere [7,8] group
• [1,2,3,8] does not adhere [7,4] group
• [1,2,7,4] does not adhere [6,3] group
• [1,2,7,8] does not adhere [6,3] group
• [1,6,3,4] does not adhere [5,2] group
• [1,6,3,8] does not adhere [5,2] group
• [1,6,7,4] does not adhere [5,2] group
• [1,6,7,8] does not adhere [5,2] group
• [5,2,3,4] does not adhere [7,8] group
• [5,2,3,8] does not adhere [7,4] group
• [5,2,7,4] does not adhere [6,3] group
• [5,2,7,8] does not adhere [6,3] group
• [5,6,3,4] does not adhere [7,8] group
• [5,6,3,8] does not adhere [7,4] group
• [5,6,7,4] does not adhere [3,1] group
• [5,6,7,8] does not adhere [3,1] group

Since non of the possible combinations work the result is False.