Cycle Contraction Path Count

Given an undirected graph with n vertices and m edges. A cycle is a set of vertices connected by edges that form a loop. In this problem, every cycle in the graph is contracted into a single vertex. The weight of the contracted vertex is the number of original vertices in that cycle (or the vertex itself if it was not part of any cycle).

After contracting all cycles, the graph becomes a tree (or a forest). You are then given q queries. Each query consists of two vertices (a and b, from the original graph). For each query, first determine the contracted vertices that a and b belong to. Then, in the tree of contracted vertices, find the unique simple path between these two nodes and sum up their weights. Finally, output the sum in binary (base-2) notation (without any prefix).

Note: Input vertices are 1-indexed.

inputFormat

The first line contains two integers n and m (number of vertices and edges).
Then m lines follow. Each line contains two integers u and v indicating there is an undirected edge between vertices u and v.
The next line contains an integer q, the number of queries.
Each of the next q lines contains two integers a and b, representing a query.

outputFormat

For each query, output a line containing a binary string which is the binary representation of the sum of weights of the contracted vertices on the unique path between the contracted vertex containing a and the contracted vertex containing b (including both endpoints).

sample

4 4
1 2
2 3
3 1
3 4
1
1 4

100