7 人解决，12 人已尝试。
20 份提交通过，共有 49 份提交。
6.9 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
Mark is a pretty cool guy - he programs computers. Because it’s all the rage these days, he has decided to write a social-networking web2.0 application. In a social-networking application, users may open accounts and tell the system which other users they consider as friends. This friendship information defines the friendship graph of the network.
An important feature of social networking applications is that whenever a user visits the page of another user, the system will determine whether there is a path in the friendship graph from the first to the second user. If so, one such a friendship path is displayed.
Mark’s social-networking application is very popular, but as it turns out computes friendship paths very slowly. In many cases however, there does not even exist a friendship path between users. Thus, Mark has the great idea check if a path exists, before actually computing it. He figures that checking for the existence of a path only should be much faster. This is where you come in.
Given the number of users, the information which users are friends and a list of pairs of users, you are to decide for which of those pairs there are paths in the friendship graph.
The first line contains the number of scenarios.
Every scenario consists of a single line containing the number 1 <=n <= 10^6 of users in the system. The number of friendships 1 <=k <=10^5 follows on a single line, followed by k lines with two numbers 0 <=a; b < n separated by a space. Each of these lines defines a direct friendship relation between user a and b. Finally, the number of requests 1<=m <=10^5 is on a single line, followed by m pairs of numbers u; v separated by spaces. Each of these pairs is a request to determine if there is a friendship path between the users u and v a.
The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario counting from 1.
For each request, print a single line with either the number 1 if the two users in this request are connected, or 0 otherwise. Every scenario is finished by a blank line.
2 3 1 0 1 2 0 1 1 2 5 3 0 1 1 2 3 4 2 0 2 1 3
Scenario 1: 1 0 Scenario 2: 1 0
7 人解决，12 人已尝试。
20 份提交通过，共有 49 份提交。
6.9 EMB 奖励。
创建: 16 年，4 月前.
修改: 7 年，3 月前.
最后提交: 4 年前.
来源: TUD Programming Contest 2008 (Training Session), Darmstadt, Germ