Circular Seating Arrangement

You are given a set of guests and pairs of guests who know each other. Your task is to determine if there exists a way to seat all the guests around a circular table such that each guest is adjacent to only guests they know.

This problem can be modeled as finding a Hamiltonian cycle in an undirected graph. The graph \(G=(V,E)\) is defined as follows:

• \(V = \{1, 2, \dots, n\}\) represents the guests.
• An edge \((a, b) \in E\) exists if guest \(a\) and guest \(b\) know each other.

You need to find a permutation \(P = (p_1, p_2, \dots, p_n)\) of \(V\) such that for every \(1 \leq i \leq n\), there is an edge between \(p_i\) and \(p_{i+1}\) (with the convention that \(p_{n+1} = p_1\)). If such a cycle exists, output one valid arrangement. Otherwise, output "No arrangement possible".

inputFormat

The input is given from standard input and consists of:

1. An integer \(n\) representing the number of guests.
2. An integer \(m\) representing the number of pairs of guests who know each other.
3. \(m\) lines follow, each containing two integers \(a\) and \(b\) indicating that guest \(a\) and guest \(b\) know each other (the relationship is bidirectional).

outputFormat

If a valid circular seating arrangement exists, output the sequence of guest numbers in one line separated by spaces. Otherwise, output "No arrangement possible".

6
7
1 2
2 3
3 4
4 5
5 6
6 1
1 4

1 2 3 4 5 6