적진 침투

두 사람이 하는 새로운 게임은 두 나라가 한 영토를 두고 싸우는 상황을 모의한다. 이 영토에는 진지를 세우기 적합한 전략 위치가 여러 개 있다. 두 플레이어는 번갈아 가며 이 위치 중 하나에 진지를 세운다.

영토에는 또한 두 위치를 잇는 길이 여러 개 있다. 플레이어가 새 진지를 세울 때마다, 그 플레이어는 인접한 길 중 적진으로 이어지는 길마다 작은 병력을 보낸다. 각 병력은 적진을 습격한다. 길마다, 그 길의 양 끝 위치 중 나중에 점령된 위치를 차지한 플레이어가 그 길을 따라 최대 한 번 습격할 수 있다. 모든 전략 위치가 점령되면 게임이 끝난다. 습격을 가장 많이 한 플레이어가 이긴다.

두 플레이어가 최적으로 플레이한다고 할 때, 누가 이기는가?

첫 줄에 전략 위치의 개수 $n$ ($1 \leq n \leq 20$)과 길의 개수 $m$ (0 \leq m \leq rac{n(n-1)}{2})이 정수로 주어진다.

이어지는 $m$개의 줄에는 각각 두 정수 $a$와 $b$ ($1 \leq a, b \leq n$, $a\neq b$)가 주어진다. 이는 위치 $a$와 위치 $b$ 사이에 길이 있다는 뜻이다.

두 위치를 잇는 길은 최대 하나이다.

먼저 시작하는 플레이어가 이기면 player 1을, 나중에 시작하는 플레이어가 이기면 player 2를 출력한다. 비기면 tie를 출력한다.