Tree Path Game

This is a two‐player game played on a tree. Bob moves first. In each turn, the current player must mark an edge on the tree that has not been marked before. However, after every move, there must exist a simple path (which may pass through unmarked edges) that traverses all the marked edges. If a player cannot make a move, they lose.

A move is legal if marking the edge keeps the set of marked edges contained in some simple path of the tree. Once an edge is marked, the structure of marked edges will always form a chain (a simple path). After the first move (choosing an edge (u, v)), the game splits into two independent "extension" games at the two endpoints u and v. For an endpoint vertex v (with the connecting edge coming from its neighbor p), the possible moves are to extend the chain via any edge incident to v except the edge to p. We define the Grundy value for such an endpoint as:

$G(v,p)=\mathrm{mex}\{ G(w,v) \mid w \in \mathrm{adj}[v]\setminus\{p\} \}$

When Bob makes the first move by marking an edge e = (u,v), the game splits into two parts with Grundy values G(u,v) and G(v,u). However, note that in normal play the next player loses if they face a P-position (i.e. a position with nim-sum 0). Hence, Bob has a winning strategy if he can choose an edge such that:

$G(u,v) \oplus G(v,u)=0$

Your task is: given a tree, determine if there exists an edge (u, v) for which G(u,v) \oplus G(v,u)=0. If such an edge exists (meaning Bob has a winning move), output Play now; otherwise, output Restart.

inputFormat

The first line contains a single integer n (the number of nodes in the tree). The next n-1 lines each contain two integers u and v describing an edge between nodes u and v (1-indexed).

outputFormat

Output a single line: Play now if Bob has a winning strategy (i.e. there exists an edge (u, v) such that G(u,v) \oplus G(v,u) = 0), otherwise output Restart.

sample

2
1 2

Play now