It's the end of the midterms in the Middle Earth Technical University and blurbian warriors are celebrating with giving feasts. However, there are only a 2 days of time before the hunting exams start and since blurbians don't want to get too full for their hunting exams, they will only attend to a single feast in a day. So, they can attend a maximum of 2 feasts in those 2 days. Blurbians also do not want to hang out with the same blurbians over and over again, so no 2 blurbians go to the same feasts twice.

Sinanto, as the smartest blurbian, wanted to keep his fitness for the exams and haven't attended any of those feasts. He wanted to learn which of his \(N\) friends encountered each other in the feasts and started creating a list. However, he noticed that some of the blurbians were so into eating that they might mix up who they had eaten with. After learning this Sinanto can't be sure that the list he has is a valid list of encounters. A valid list means that every encounter is possible with the 2 days of feasting with no missing encounters in the list.

For example let's think that sino, auo, and fako say that they have encountered each other, and auo says that she also encountered eco. It's possible with auo, sino, and fako having a feast together on the first day, and eco and auo having another feast on the second day. However, if sino says that he also encountered eco, it's no possible since he cannot be in the same feast with auo on the second day.

Can you help Sinanto, and determine that the information he gathered is valid or not?

• There is no limit to the number of attendants in a feast.
• There is no limit to the number of simultaneous feasts.

Input

The first line will contain 2 integers, \(N\) and \(M\).

In the following \(M\) lines, there will be 2 names, denoting the blurbians who remember eating together.

• \(1 \leq \mathbf{N} \leq 300\)
• \(1 \leq \mathbf{M} \leq 1000\)
• \(1 \leq \mathbf{len(A_i)} \leq 5\)

Output

Only 1 character should be printed. "1" if the information is consistent, "0" otherwise.

Examples

Input:

3 3
uco bico
bico dero
uco dero

Output:

1

Input:

4 5
sino fako
sino auo
fako auo
auo eco
sino eco

Output:

0

Explanation

1st Input

There are 3 blurbians whose names are uco, bico, and dero. Every pair of those blurbians think that they have encountered during the 2 days of feasts.

The information is possible, hence consistent. One possible way of encounters is that 3 of them join the same feast on the first day and don't attend a feast on the first day.

2nd Input

There is no possible way of the listed blurbians encountering in the 2 days of feasts. So, the information Sinanto gathered isn't consistent.