Вечірка#4327

Вечірка

1 секунда

64 мегабайти

Дуже складна

Байтасар планує влаштувати вечірку. Звісно, він хоче, щоб вона вдалася. Більше того, Байтасар переконаний, що для цього достатньо, щоб усі запрошені гості знали одне одного. Наразі він складає список своїх друзів, яких хотів би запросити.

У Байтасара є $n$ друзів, де $n$ ділиться на $3$ . На щастя, більшість із друзів Байтасара знайомі між собою. До того ж, Байтасар пригадує, що якось відвідував вечірку, на якій було $(2/3) \cdot n$ (2/3) \cdot n його друзів, і всі вони знали одне одного. На жаль, Байтасар не пам’ятає нічого іншого з тієї вечірки... Зокрема, він не пам’ятає, які саме його друзі тоді були.

Байтасар не наполягає на масштабній вечірці, але хоче запросити щонайменше $n /3$ своїх друзів. Він не знає, як їх обрати, тому просить вас допомогти.

Вхідні дані

Перший рядок містить два цілі числа $n$ та $m$ ( $3 \leq n \leq 1000$ 3 \leq n \leq 1000, $0 \leq m \leq n (n - 1) /2$ 0 \leq m \leq n(n-1)/2), розділені пробілом. Вони означають кількість друзів Байтасара та кількість пар його друзів, які знайомі між собою. Друзів Байтасара пронумеровано від $1$ до $n$ .

Кожен із наступних $m$ рядків містить два цілі числа, розділених пробілом. Числа в $(i + 1)$ (i+1)-му рядку ( $i = 1, 2, \dots, m$ i = 1, 2, \ldots, m) — це $a_{i}$ a_i та $b_{i}$ b_i ( $1 \leq a_{i} < b_{i} \leq n$ 1 \leq a_i < b_i \leq n), що означає: особи $a_{i}$ a_i та $b_{i}$ b_i знайомі між собою. Кожна пара зустрічається у вхідних даних не більше одного разу.

Вихідні дані

Виведіть $n /3$ чисел у зростаючому порядку в одному рядку, розділивши їх пробілами. Ці числа мають означати номери друзів Байтасара, яких він має запросити на вечірку. Якщо існує декілька розв’язків, виведіть будь-який з них.

Приклади

Приклад 1