Panda Guru LogoPanda
Guru

Goldman Sachs OA problem

Round 1

Questions: Anaximander was a Greek traveller who visited many countries during his lifetime. He left behind a vivid description of the countries he visited in the form of a graph where each node represents a city and the edges represent the roads between them.

It is also known that all the cities of a country are directly connected to each other through bidirectional roads. Some other interesting features of these countries were that there were at least 3 cities in each country, with exactly one road between any two countries and it was possible to start the journey from one country and visit any other country.

With the help of the above information, you need to determine the number of countries that Anaximander visited.

Input Format: The first line of the input contains one integer T - the number of test cases. Then T test cases follow.

The first line of each test case contains 2 space-separated integers N and M - the total number of cities and roads respectively.

The next M lines contain 2 space-separated integers - Ui and Vi representing the cities at the ends of the ith bidirectional road.

Output Format: For each test case, print on a new line the number of countries visited by Anaximander.

Constraints: 1 <= T <= 100

3 <= N <= 1000

1 <= Ui, Vi <= N

It's guaranteed that the sum of N over all test cases <= 1000 and there are no self edges or multiple edges in the graph.

Hints to Solve the Problem:

Candidate's Approach

No approach provided.

Interviewer's Feedback

No feedback provided.