Consider an undirected graph with \(N\) vertices and \(M\) edges where the \(i\)-th edge connects Vertex \(A_i\) and Vertex \(B_i\). If the \(i\)-th edge in this graph is a bridge, the \(i\)-th edge in the undirected graph corresponding to any binary sequence of length \(M\) will always be a bridge. Actually, it is possible to make all other edges (except trivial edges) non-bridges by appropriately choosing the binary sequence.

Each connected component after removing the bridges can be independently treated, so we may assume that the graph is connected and has no bridges. Then, it is possible to turn the graph into a strongly connected direct graph by appropriately directing each edge. One way to do so is to take a DFS tree, and direct the edge from the child to the parent for each edge used in the tree and from the deeper vertex to the shallower vertex for each back-edge.

From these directions, we construct a binary sequence as follows:

• if the \(i\)-th edge is directed from Vertex \(A_i\) to Vertex \(B_i\), the \(i\)-th character is 0;
• if the \(i\)-th edge is directed from Vertex \(B_i\) to Vertex \(A_i\), the \(i\)-th character is 1.

Let us verify that this binary sequence satisfies our requirement. Assume that there are two or more vertices. (For the case of one vertex, there would be one bridge.) Then, from the fact that the original graph has no edges, the only edges that could be a bridge are those connecting Vertex \(j\) and Vertex \((j+N)\). Here, there is a cycle containing Vertex \(j\) since the previous directed graph is strongly connected. By seeing the edges used in this cycle, we can see that Vertex \(j\) and Vertex \((j+N)\) would be connected even after removing the edge between them. Therefore, the undirected graph corresponding to this binary sequence has no edges.