CF603E Pastoral Oddities

In the land of Bovinia there are $ n $ pastures, but no paths connecting the pastures. Of course, this is a terrible situation, so Kevin Sun is planning to rectify it by constructing $ m $ undirected paths connecting pairs of distinct pastures. To make transportation more efficient, he also plans to pave some of these new paths. Kevin is very particular about certain aspects of path-paving. Since he loves odd numbers, he wants each pasture to have an odd number of paved paths connected to it. Thus we call a paving sunny if each pasture is incident to an odd number of paved paths. He also enjoys short paths more than long paths, so he would like the longest paved path to be as short as possible. After adding each path, Kevin wants to know if a sunny paving exists for the paths of Bovinia, and if at least one does, the minimum possible length of the longest path in such a paving. Note that "longest path" here means maximum-weight edge.

N/A

N/A

For the first sample, these are the paths that Kevin should pave after building the $ i $ -th path: 1. No set of paths works. 2. Paths 1 (length $ 4 $ ) and 2 (length $ 8 $ ). 3. Paths 1 (length $ 4 $ ) and 2 (length $ 8 $ ). 4. Paths 3 (length $ 2 $ ) and 4 (length $ 3 $ ). In the second sample, there never exists a paving that makes Kevin happy.