Description:
You are given a complete bipartite graph with $$$2n$$$ nodes, with $$$n$$$ nodes on each side of the bipartition. Nodes $$$1$$$ through $$$n$$$ are on one side of the bipartition, and nodes $$$n+1$$$ to $$$2n$$$ are on the other side. You are also given an $$$n \times n$$$ matrix $$$a$$$ describing the edge weights. $$$a_{ij}$$$ denotes the weight of the edge between nodes $$$i$$$ and $$$j+n$$$. Each edge has a distinct weight.
Alice and Bob are playing a game on this graph. First Alice chooses to play as either "increasing" or "decreasing" for herself, and Bob gets the other choice. Then she places a token on any node of the graph. Bob then moves the token along any edge incident to that node. They now take turns playing the following game, with Alice going first.
The current player must move the token from the current vertex to some adjacent unvisited vertex. Let $$$w$$$ be the last weight of the last edge that was traversed. The edge that is traversed must be strictly greater than $$$w$$$ if the player is playing as "increasing", otherwise, it must be strictly less. The first player unable to make a move loses.
You are given $$$n$$$ and the edge weights of the graph. You can choose to play as either Alice or Bob, and you will play against the judge. You must win all the games for your answer to be judged correct.
Input Format:
None
Output Format:
None
Note:
The first example has two test cases. In the first test case, the graph looks like the following.
In the sample output, the player decides to play as Alice and chooses "decreasing" and starting at node $$$3$$$. The judge responds by moving to node $$$6$$$. After, the player moves to node $$$2$$$. At this point, the judge has no more moves (since the weight must "increase"), so it gives up and prints $$$-1$$$.
In the next case, we have two nodes connected by an edge of weight $$$1$$$. The player decides to play as Bob. No matter what the judge chooses, the player can move the token to the other node and the judge has no moves so will lose.