Party Invitations

Byteasar wants to throw a party and he believes that for the party to be successful, all invited guests should know each other (i.e. form a clique). He has n friends (where n is divisible by 3) and he recalls that at one party he attended, there was a group of \(\frac{2}{3}n\) friends all knowing one another. Unfortunately, he does not remember which friends were present that day. However, he would like to invite at least \(\frac{n}{3}\) of his friends.

Your task is to help Byteasar choose a subset of his friends (by their indices) such that:

• The number of invited friends is at least \(\frac{n}{3}\).
• Any two invited friends know each other (i.e. the chosen subset forms a clique).

You are given the friendship relations among the n friends. It is guaranteed that there exists a clique of size \(\frac{2}{3}n\) in the graph. Use this fact to design an algorithm that outputs a valid set of friends.

inputFormat

The first line contains two integers n and m (with \(n\) divisible by 3), where n is the number of friends and m is the number of friendship relations.

Each of the next m lines contains two integers u and v (1 ≤ u, v ≤ n, u \(\neq\) v), which means that friend u and friend v know each other. The relation is bidirectional.

outputFormat

On the first line, output an integer k (\(k \geq \frac{n}{3}\)) – the number of friends that Byteasar will invite. On the second line, output k distinct integers representing the indices of the friends in the chosen clique. The order of indices does not matter.

sample

3 3
1 2
1 3
2 3

3
1 2 3