Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Christmas Game
Description Harry and Sally were playing games at Christmas Eve. They drew some Christmas trees on a paper: Then they took turns to cut a branch of a tree, and removed the part of the tree which had already not connected with the root. A step shows as follows: Sally always moved first. Who removed the last part of the trees would win the game. After a while, they all figured out the best strategy and thought the game was too simple for them. Harry said, “The Christmas trees should have some gifts in them!” So Sally drew some gifts (simple polygons) in the initial trees: You may assume the initial picture is a tree with some simple polygons, in which each edge is involved in at most one polygon. We also know that every polygon has only one node involved in the main tree (the hanging point of the giftJ) .In every sub-tree (connected subgraph), there was one and only one node representing the “root”. According to these assumptions, following graphs will never appear: Sally and Harry took turns (Sally was always the first person to move), to cut an edge in the graph, and removed the part of the tree that no longer connected to the root. The person who cannot make a move lost the game. Your job is to decide who will finally win the game if both of them use the best strategy. Input The input file contains multiply test cases. Output For each test case, output the name of the winner. Sample Input 2 2 1 1 2 4 4 1 2 2 3 2 4 3 4 Sample Output Sally Hint The sample graph is Source POJ Founder Monthly Contest – 2008.12.28, Yaojinyu |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator