5978번 - Odd degrees 스페셜 저지다국어

The cows are being invaded! Their republic comprises N (1 <= N <= 50,000) towns that are connected by M (1 <= M <= 100,000) undirected paths between two towns A_i and B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i; 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

• Line 1: Two space-separated integers: N and M
• Lines 2..M+1: Line i+1 contains two space-separated integers: A_i and B_i

• Line 1: A single integer that is the number of paths to keep. If no subset exists output only a single line with the integer -1.
• Lines 2..K+1: Each line contains an index of an path to keep, in the range 1..M. These indices must be pairwise distinct.