Politicians

One more parliamentary election is behind us. The first job of the freshly sworn in prime minister Rydzio is to form a cabinet. He decided to pick his ministers from the $n$ members of his own party, numbered $0$ through $n-1$.

The trouble is that every candidate handed Rydzio a list of party colleagues he refuses to work with. The relation goes both ways. If A refuses to work with B, then B refuses to work with A. On top of that, every member threatened to join the opposition if he is left out, so all $n$ of them have to get a post.

Rydzio did not think for long and proposed the following compromise.

1. Some of the candidates join the cabinet. The rest go to the board of a Very Important Company.
2. Neither the cabinet nor the board may seat three people who all refuse one another. In other words, there are no three people A, B, C assigned to the same institution such that A refuses B, A refuses C, and B refuses C.

Two people who refuse each other may still sit in the same institution. Rule 2 forbids only a trio in which all three refuse one another. One of the two institutions may end up empty.

The leader of the opposition announced that he sees no difficulty here. He said that if the whole party did not have to be placed, he could split it into the cabinet, the board and a group of unselected members so that no two people who refuse each other share a group. You may assume he is telling the truth.

Rydzio wants the cabinet to be as large as rule 2 allows. Find the largest possible number of ministers.

The first line contains the number of party members $n$ and the number of pairs that refuse to work together $m$, separated by a single space. ($1 \le n \le 18$, $0 \le m \le n(n-1)/2$)

Each of the next $m$ lines contains two integers $a$, $b$ ($0 \le a < b < n$). They mean that members $a$ and $b$ refuse to work together. No pair is given twice.

Print on one line the largest number of members that can sit in the cabinet. Neither the cabinet nor the board may contain three people who all refuse one another, and every member left out of the cabinet goes to the board.