Taofiq the House Prefect

shajia Criterion 2020 Round 7
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 $8$ and he has $3$ friends to call whose roll numbers are $5$, $2$ and $9$; then:

  • Taofiq will call the friend with roll number $2$,
  • then he will call the friend roll number $5$ and finally,
  • he will call the friend with roll number $9$.

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 $T$ ($1 ≤ T ≤ 10$), denoting the number of test cases. The first line of each case contains two integers $n$ ($2≤ n ≤ 100000$) and $m$ ($0 ≤ m ≤ 1000000$). Here, $n$ represents the number of members in Taofiq’s team and $m$ represents the number of direct friendships among the team members. Then there will be $m$ lines. Each of these m lines contain two integers $x$ ($0 ≤ x < n$) and $y$ ($0 ≤ y < n$), that represents friendship between team member $x$ and team member $y$. After the $m$ lines, there will be another integer $Q$ ($1 ≤ Q ≤ 10$) that represents queries. Then there will be $Q$ lines where each of the line represent a query in the format $a$ $b$ ($0 ≤ a,b < n$).

Taofiq will always have the roll number $0$.


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:


Login to submit.


89% Solution Ratio
mohanr7073Earliest, Sep '20
monon_mirzaFastest, 0.1s
Md_Siam07Lightest, 6.3 MB
Tahmid690Shortest, 916B
Toph uses cookies. By continuing you agree to our Cookie Policy.