Social Networking Application

Since childhood, Sanggeun has shown remarkable talent for computer programming, and he has always wanted to build a social networking website. After three years of carefully studying various services, he now wants to build his own new social networking application.

Users sign up for the application and then add people they know in real life as friends. From this friendship information, a friendship graph can be built.

The most important feature of the application is this: when one user visits another user's page, it shows a path connecting the two people in the friendship graph. If there is no such path, nothing is shown.

As the service grew popular and the number of users increased, this feature became slower and slower. The reason is that, when there is no path between two people, the program spends far too long searching the whole graph trying to find one. So Sanggeun wants to precompute whether a path between two people exists.

You are given the number of users and their friendships. For each given pair of people, determine whether they are connected in the friendship graph (that is, whether a path between them exists).

The input consists of several test cases. The first line of the input contains the number of test cases $T$ ($T \ge 1$).

The first line of each test case contains the number of users $n$ ($1 \le n \le 10^6$). The second line contains the number of friendships $k$ ($1 \le k \le 10^5$). Each of the next $k$ lines contains two integers $a$ and $b$ ($0 \le a, b < n$), meaning that users $a$ and $b$ are friends. The next line contains the number of pairs to check $m$ ($1 \le m \le 10^5$). Each of the next $m$ lines contains two integers $u$ and $v$ describing a pair to check.

For each test case, first print Scenario i:, where $i$ is the test case number starting from $1$. Then, for each given pair, print $1$ if there is a path connecting the two people and $0$ otherwise, one per line.

Print one blank line between the outputs of consecutive test cases.