The game Alice and Bob play in this task is a classic game in Combinatorial Game Theory (CGT), known under the name Green Hackenbush. (Why "green"? There is a generalization of this game, where each of the edges is colored red, green or blue. Any player may chop green edges, but only player A may chop the red ones and only player B may chop the blue ones.)
This game is treated in detail for example in the book Berlekamp, Conway, Guy: Winning Ways for your mathematical plays or in the electronic text Ferguson: Game Theory (it can be downloaded from Thomas Ferguson's homepage). We assume that the reader already understands the basics in CGT, such as what is a Sprague-Grundy (SG) value of a position, what is a sum of games and how to compute its SG value. If you don't have the necessary basics in CGT, we suggest that you read the first chapters of any of the above-mentioned books before reading this solution. Note that before the contest we considered this problem to be the hardest one in this year's problem set because you need this non-trivial knowledge to solve it.
The most simple version of this game is when the given graph is a star "growing out" of the vertex 1. If we imagine vertex 1 being the ground, this graph can be imagined as several bamboo stalks growing from the ground. Consider a game with N bamboo stalks, k-th of them having A[k] edges. This game is isomorphic to the classic game of NIM with N heaps of matches, k-th of them containing A[k] matches. Remember that the SG value of a position in NIM is the "NIM sum" (bitwise xor) of the sizes of the heaps (or in our case of the lengths of the bamboo stalks).
We will now generalize the game to arbitrary trees rooted at the vertex 1. To do this, we will use the following lemma. (If you are interested, you may find proofs of all our claims at the end of this solution, as the proofs are not necessary to implement a solution.)
Colon Principle. Consider a fixed graph G and select its arbitrary vertex v. Now take two graphs H1, H2 such that their SG value is the same. Let Gi be the graph obtained from G by attaching Hi to the vertex v (vertex v in G and vertex 1 in Hi merge into one vertex). Then also G1 and G2 have the same SG value.
Now consider an arbitrary tree rooted at the vertex 1. We will try to reduce this tree to an equivalent bamboo stalk (thereby determining its SG value). Take an arbitrary vertex in the tree. Several subtrees come together at this vertex. Suppose we already know their SG values. The Colon Principle states that we may replace each of them by the corresponding bamboo stalk. Now take the graph H to be the set of all the bamboo stalks. We already know how to compute the SG value of H -- H is a sum of games on the bamboo stalks, therefore its SG value is the "NIM sum" of the SG values of the bamboo stalks. We may now replace H by the corresponding bamboo stalk.
The implementation is trivial. We traverse the tree e.g. using depth-first search and for each vertex we compute the SG value of the subtree rooted at this vertex. If we have the values for all sons si of some vertex v, we compute SG(v)=XORi (SG(si)+1). (From the Colon Principle the SG value of a tree consisting of an edge vsi and a subtree rooted at si has the SG value SG(si)+1.) If SG(1)=0, Bob wins else Alice wins. Both time and space complexity of this algorithm is linear in the size of the given graph.
This knowledge already sufficed to solve the easy input. If you took some time to look at the input data, you could easily notice that in each of the graphs the number of edges is one less than the number of vertices. From the problem statement you know that the graph is connected, therefore it has to be a tree. (There was one exception at the end -- a small graph from the sample input.)
The hard input contained general graphs. To deal with general graphs, we need another lemma. Before stating the lemma, we define the word "fuse". To fuse two vertices means to replace them by one vertex. All edges leading into them now lead to this new vertex. Each edge connecting the two fused vertices is replaced by a loop at the new vertex.
Fusion Principle. The vertices on any cycle may be fused without changing the SG value of the graph. (Note that the order in which we fuse them is not important.)
The Fusion Principle is all we need to solve the general case. Take the graph. As long as it contains a cycle, fuse its vertices. After a finite number of steps we will obtain a tree with loops at some vertices.
Now all we have to do is compute the SG value of a tree with loops. But this is easy. We may replace a loop by an edge to a new vertex. Then we may use the same algorithm as above to determine the SG value of the resulting tree. Actually we don't have to replace the loops by new edges. If there is an even number of loops at a vertex, their "contribution to its SG value" is zero, if there is an odd number of loops, their "contribution" is one.
The implementation of fusing will be a bit tricky. We will do all the steps at once. It suffices to find all bridges in the given graph. A bridge is an edge that doesn't lie on any cycle, in other words when we cut a bridge we obtain two disconnected parts of the graph. Suppose we cut all the bridges in the given graph. Consider any of the resulting components. We claim that the component may be fused to a single vertex. There is a classic algorithm to find the bridges, this algorithm is linear in the size of the graph. Contracting the components may be done in linear time, too. On the resulting tree with loops we apply the modified algorithm mentioned above. Hence we get a solution for the general case, that's linear in the size of the graph and therefore optimal.
Proof of the Colon Principle. The theorem is equivalent to the claim that the SG value of the game G1+G2 is zero. In other words, consider a game played on both G1 and G2. We have to show that this is a losing position for the first player. We will do this by showing a winning strategy for the second player. If the first player chops some edge in one of the copies of G, do the same in the other copy. This may delete both H1 and H2 from the game, but otherwise they are not altered. If the first player chops an edge in either H1 or H2, the SG values of new H1' and H2' differ. Therefore there is a move in one of them to make them equal again (because H1'+H2' is now a winning position). Make this move. When using this strategy, the second player always has a move. Therefore he is the last to move and wins.
Proof of the Fusion Principle. Suppose the contrary. Take the counterexample with the least number of edges, if there are more such counterexamples, choose the one with the least number of vertices. Call this graph G. We can deduce the following facts about G:
Every cycle in G contains the vertex 1. Again, suppose the contrary. G is connected, therefore at least one of the vertices on the cycle has to be connected to the vertex 1 (without using edges of the cycle).
If there is exactly one such point, it is an articulation. Take the "component" of G containing our cycle. It is smaller than G, therefore Fusion Principle holds and we may fuse the vertices on our cycle without changing the SG value of the "component". However from the Colon Principle we may replace the original "component" with the fused one without changing the SG value of G, which is a contradiction.
If there are more such points, take any two of them. These points are connected by at least three edge-disjoint paths. (Twice by the edges of the cycle, at least once through the rest of the graph.) But G contains no such pair of vertices.
We now know that G contains only one cycle passing through the vertex 1. There may be additional vertices and edges in G, they form trees rooted in vertices of the cycle. To finish our proof we will show that the Fusion Principle in fact holds for G.
We now have to show that G has the same SG value as the graph G' obtained from G by fusing the vertices of the only cycle in G. Take the sum of these two games, we have to show that the position is losing for the first player. If he cuts an edge in one of the trees in G or G', the second player responds by cutting the corresponding edge in the other graph. Both graphs are now smaller than G, moreover we still get one of them by fusing the vertices of the only cycle in the other one. But for graphs smaller than G the Fusion Principle applies. Therefore their SG value is the same and thus the whole position is losing.
So the first player has two options left: to cut an edge of the cycle in G or to cut one of the corresponding loops in G'. Suppose he cut an edge of the cycle in G. Thereby G is split into two trees. We have to show that this position is winning, i.e. that its SG value is non-zero. We will show that the SG value of this position is odd. Recall that when we computed the SG value of a tree, at each vertex we xor-ed some values. Now if we replace all the xors by addition, the last binary digit of the result will be the same. Knowing this, we can easily prove by induction that the parity of the SG value of a tree is the same as the parity of its number of edges. Our position consists of three trees and together they have an odd number of edges, therefore its SG value is odd.
The last option for the first player is to cut one of the loops at the vertex 1 in G'. We omit this part of the (already long) proof and leave it as an exercise to the reader.
Proof that it suffices to contract the components left after cutting all the bridges. Consider any of the components. It doesn't contain any bridges. If there is more than one vertex in the component this means that the component contains some edges between its vertices. Consider any of them. It is not a bridge, therefore it lies on some cycle. The vertices on this cycle may be fused. During the fusion no new bridges arise in the component and so we may repeat this process until the component has only one vertex left.