Company: Adobe_11july
Difficulty: medium
Road Construction for Full Connectivity Problem Description You are given N cities numbered from 0 to N-1, where each road connects two cities. Some cities may be unreachable from others. The king wants to ensure that every city is reachable from every other city. To achieve this, he can construct new roads, but he has a budget to build only K roads. These new roads must start and end at cities with odd numbers. Your task is to determine if it's possible to make the new roads such that every city becomes reachable from every other city, given the constraints. Note: There can be multiple roads between two cities. Input Format The first line contains three space separated integers N, M, and K, where N is the number of cities, M is the number of roads, and K is the number of roads the king can afford to build. The next M lines each contain two integers U and V, indicating that there exists a road between city U and city V. Output Format Print "YES" if the king can construct roads such tha