Entering Enemy Encampment

Time limit4sMemory limit1024 MB

Summary

Two players alternately claim n positions, and each trail scores for whoever claims its later endpoint while the other endpoint is an enemy camp. Find the winner under optimal play.

Level: Medium7 of 10
Topics: Game theory, Bit manipulation, Dynamic programming
Solved: No attempts yet

Problem

A new two-player game simulates two countries fighting over a territory. The territory has a number of strategic positions suitable for setting up war camps. The players take turns setting up a camp at one of these positions.

The territory also has a number of trails, each connecting two positions. Whenever a player sets up a new camp, that player sends a small group of soldiers over every adjacent trail that leads to an enemy encampment. Each group raids the enemy camp. For every trail, the player who captures the later of its two endpoints can launch at most one raid over that trail. When every strategic position has been claimed, the game ends. The player who performed the most raids wins.

Assuming both players play optimally, who wins?

Input

The first line contains two integers $n$ ( $1 \leq n \leq 20$ ) and $m$ ( $0 \leq m \leq \frac{n(n-1)}{2}$ ), the number of strategic positions and the number of trails.

Each of the next $m$ lines contains two integers $a$ and $b$ ( $1 \leq a, b \leq n$ , $a\neq b$ ), meaning there is a trail between position $a$ and position $b$ .

There is at most one trail between any pair of positions.

Output

If the first player wins, output player 1. If the second player wins, output player 2. If the players tie, output tie.

Examples3

Example 1
Input
```
3 3
1 2
2 3
1 3
```
Expected output
```
tie
```
Example 2
Input
```
2 1
1 2
```
Expected output
```
player 2
```

Example 3

Input

Expected output

player 1