Winning Start Positions in an Edge‐Deletion Graph Game

Two players play a game on a connected undirected graph with n vertices and m edges. The graph has the special property that each edge belongs to at most one simple cycle (i.e. the graph is a cactus graph). At the beginning of the game, a chip is placed on one of the vertices. Then the players take turns moving the chip along an edge that has not been used before. Once an edge is used it cannot be traversed again. The player who is unable to make a move loses the game.

Your task is to determine all starting vertices such that the first player has a winning strategy (that is, positions from which the first mover can force a win under optimal play).

In the game, when a move is made along an edge, that edge is removed from the graph. Note that even though vertices may be revisited, edges cannot. The challenge is to analyze the combinatorial game where the move choices affect the remaining graph.

More formally, given a connected undirected graph G=(V,E) with |V| = n and |E| = m, where every edge e appears in at most one simple cycle, determine all vertices v such that when the chip is initially placed at v the first player can force a win.

The game state can be modeled by a pair (v, M) where v is the current vertex and M is a bitmask representing the set of already used edges. A recursive search with memoization (or DP) over states is sufficient provided the constraints are small. (Note that in contest problems the cactus property is used to limit the complexity of the game.)

The formulas used in the solution (if any) should be written in LaTeX format. For example, if you refer to a cycle length you can write it as $L$.

inputFormat

The first line contains two integers n and m ($1 \le n, m \le 20$ assumed for the state‐space to be manageable), representing the number of vertices and edges respectively. The following m lines each contain two integers u and v ($1 \le u,v \le n$), which indicate an undirected edge between vertices u and v.

outputFormat

Output the winning starting positions (i.e. vertex numbers) for which the first player can force a win if the chip is initially placed on that vertex. The vertices should be printed in increasing order separated by a single space. If there is no winning starting position, output an empty line.

sample

2 1
1 2

1 2