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.