The cows are being invaded! Their republic comprises N () towns that are connected by M () undirected paths between two towns and ( no duplicate paths will occur). However the republic is not necessarily connected--there may be pairs of towns that are unable to reach each other through the paths.
The cows know their invaders plan to conduct an inventory of every path within their republic, so they are willing to shut down various paths to make it as difficult as possible for their invaders to do so.
Please help the cows find a way to shut down a subset of the paths such that each town has an odd number of remaining paths connected to it, or determine if no such subset exists.
For example, consider the following cow republic:
1---2 \ / 3---4 If we keep the paths 1-3, 2-3, and 3-4, and remove the path 1-2, then towns 1, 2, and 4 will be an endpoint of exactly one path, whereas town 3 will be an endpoint of three paths:
1 2 \ / 3---4