Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Taofiq the House Prefect

By shajia · Limits 2s, 512 MB

Tomorrow is a very special day for Taofiq. He is participating in an intra school quiz contest. As he is one of the house prefects of his school, he has a lot of responsibilities. Furthermore, he needs to do well in the contest. Before any special event of his life, Taofiq takes some time for himself to contemplate. It helps him to think about himself and generate new ideas. Today is no exception. He has found a magic trick that will help his house team to do well in the contest. Now he is feeling sleepy and can not reach every member of his team. So he comes up with a different approach to propagate the magic trick to everyone.

Since everyone on his team has a mobile phone, he can propagate his message to each of them. But he decides to call only his friends from the team. Then every one of his friends will call their friends. In this way, he will communicate with the team members and propagate the news. There is another rule, everyone including him will call their friends with the ascending order of their roll numbers.

Suppose, the roll number of Taofiq is 88 and he has 33 friends to call whose roll numbers are 55, 22 and 99; then:

  • Taofiq will call the friend with roll number 22,
  • then he will call the friend roll number 55 and finally,
  • he will call the friend with roll number 99.

Everyone on his team will follow the same rule. For simplicity, a person will try to call all of his friends sequentially. Also, a person will call his friends only after those who have received the call before him are finished calling. If someone has already got the messages from a friend, then he will only call his friends and will not pick up any other phone calls. So, if someone calls his friend but finds him unreachable, he will safely assume that the friend has already got the message.

Being a good house prefect, Taofiq already knows which team member is supposed to call which other members. Before the start of the contest, he will make some queries about the conversations to ensure that everything is done perfectly. In each query, he will mention two team members x and y and will ask whether they had a phone conversation or not.

As Taofiq is busy with other work, he needs your help. Write a program which will help Taofiq to make the queries easily.


The first line contains an integer TT (1T101 ≤ T ≤ 10), denoting the number of test cases. The first line of each case contains two integers nn (2n1000002≤ n ≤ 100000) and mm (0m10000000 ≤ m ≤ 1000000). Here, nn represents the number of members in Taofiq’s team and mm represents the number of direct friendships among the team members. Then there will be mm lines. Each of these m lines contain two integers xx (0x<n0 ≤ x < n) and yy (0y<n0 ≤ y < n), that represents friendship between team member xx and team member yy. After the mm lines, there will be another integer QQ (1Q101 ≤ Q ≤ 10) that represents queries. Then there will be QQ lines where each of the line represent a query in the format aa bb (0a,b<n0 ≤ a,b < n).

Taofiq will always have the roll number 00.


In the output, for each case, print the case number on a line by itself. For each query, print Yes on a line, if there was a conversation between a and b, or print No otherwise.


9 10
0 3
0 8
1 0
1 3
1 5
2 4
3 2
4 7
5 2
2 6
1 3
0 6
4 5
4 7
6 7
6 8
0 1
1 2
1 3
1 5
2 4
5 4
5 3
4 3
1 0 
Case 1:
Case 2:



90% Solution Ratio

mohanr7073Earliest, Sep '20

user.953511Fastest, 0.1s

Md_Siam07Lightest, 6.3 MB

Tahmid690Shortest, 916B


Login to submit


The main purpose of this problem is to identify the phone calls among two people. First, we have to ...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.