One day, Flyvanintroduced a new game to his two friends, Oregon Maple and Grape Skin. The gameis quite simple. Given an N-sized grids, like the figure A shown below (as N =4). The blue points are the places the first player can choose, and the redpoints are the places the second player can choose.
<!--[endif]-->
In the game, thetwo players take turns to choose two points to get connected by a stick. Thetwo chosen points’ distance should be exactly one-unit length. The first player’sgoal is to create a ‘bridge’ that connects a most left point and a most rightpoint. The second player’s goal is to create a ‘bridge’ that connects a mosttop point and a most bottom point. Figure B shows a possible result (the firstplayer won). In addition, the stick shouldn’t get crossed.
Now Flyvan willgive the number N, and his two friends will play the game. Both of the twoplayers will choose the best strategy. You can bet on one player, and if hewins the game, you’ll get twice money you bet~
Since you are atalented programmer, you surely won’t just do gambling. Please write a programto find out the player who you should bet on. As Oregon Maple is elder, he willalways play first.