favorite We need a little bit of your help to keep things running, click on this banner to learn more



In the fairy kingdom N cities. Some pairs of cities connected by roads, with one and that same pair of cities can connect several roads. Outside the cities the roads do not intersect. On every road you can go in any direction. Help the King to determine skoloi still need to build roads in the kingdom, that His Majesty was able to travel on all roads, not prooezzhaya twice on any of them. Usually (see example), he has to visit each city. Travel King should nachinatsya and ends with in the same city.


You enter the first number in the kingdom cites N (1N100) and the number of city pairs K (1K10000). Then, in groups of 3 to the number you enter the number of towns and number of roads connecting them (all the numbers do not exceed 100). All numbers rozdeleny space.


You draw the smallest possible number of roads.

Time limit 1 second
Memory limit 64 MiB
Input example #1
7 6 1 2 1 1 3 1 4 1 3 4 2 5 3 4 3 5 6 2
Output example #1