We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Repair Roads

Repair Roads

Problem
Submissions
Leaderboard
Discussions

The country of Byteland contains cities and bidirectional roads. There is a path between any two cities. The roads in Byteland were built long ago, and now they are in need of repair. You have been hired to fix all the roads. You intend to do this by dispatching robots on some of the roads. Each robot will repair the road he is currently on and then moves to one of the adjacent unrepaired roads. After repairing that, it will move to another adjacent unrepaired road, repair that and so on.

Two roads are adjacent if they have the same city at one of their endpoints. For the process to be efficient, no two robots will ever repair the same road, and no road can be visited twice. What is the minimum number of robots needed to accomplish the task?

Input Format

The first line contains the number of test cases . test cases follow. The first line of each test case contains , the number of cities in Byteland. The cities are numbered . The following lines contain the description of the roads. The line contains two integers and , meaning that there is a road connecting cities with numbers and .

Constraints

Output Format

Print lines, one corresponding to each test case containing the required answer for that test case.

Sample Input

3  
4  
0 1  
0 2  
0 3  
6  
0 1  
1 2  
2 3  
2 4  
4 5  
7  
0 1  
1 2  
2 3  
2 4  
4 5  
3 6

Sample Output

1  
1  
2

Explanation

For the first case, one robot is enough to repair all roads:
For the second case, one robot is again enough:
The the third case, there is no way to repair all the roads with one robot and at least two are needed.

Author

HackerRank

Difficulty

Hard

Max Score

80

Submitted By

2163

Need Help?


View discussions
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy