Problem Statement

Road Construction for Full Connectivity Problem Description There are N cities labeled 0 through N-1, and existing roads each connect a pair of these cities. As things stand, some cities may have no path to others. A regional planner wants every city to be able to reach every other city, purely by traveling along roads. The planner is allowed to add brand-new roads, but the budget covers only K of them, and each new road's two endpoints must both be odd-numbered cities. Decide whether adding at most K such roads can make the whole network connected, given these restrictions. Note: There can be multiple roads between two cities. Input Format Line one gives three integers N, M, and K separated by spaces: N cities in total, M roads already built, and K new roads the budget allows. Each of the next M lines holds two integers U and V, meaning a road already links city U and city V. Output Format Output "YES" when the roads can be added so the whole city network becomes connected under the s