/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
頂点に 1 から N の番号が、辺に 1 から M の番号がついた N 頂点 M 辺からなる単純無向グラフが与えられます。 i 番目の辺は頂点 U_i と頂点 V_i を結んでいます。最初、 G は奇閉路を持ちません。
このグラフ G を使って、青木君と高橋君がゲームをします。先手の青木君から順に交互に以下の操作を行います。
- 1 \leq i < j \leq N を満たす整数の組 (i,j) であって、以下の条件をともに満たすものを選び、頂点 i と頂点 j を結ぶ辺を G に追加する。
- G は頂点 i と頂点 j を結ぶ辺を持たない
- 頂点 i と頂点 j を結ぶ辺を G に追加しても、奇閉路ができない
操作を行えなくなった方が負けであり、負けでない方が勝ちです。
両者が最適に行動したとき、どちらが勝つか判定してください。
奇閉路とは？
G の頂点の列 (v_0,v_1,\ldots,v_k) が以下の条件を全て満たすとき、かつ、そのときに限りこの列を G の奇閉路といいます。
- k は奇数である。
- v_0=v_k である。
- 全ての 1\leq i \leq k に対して、v_{i-1} と v_{i} を結ぶ辺が存在する。
制約
- 1 \leq N \leq 2\times 10^5
- 0 \leq M \leq 2\times 10^5
- 1 \leq U_i < V_i \leq N
- 与えられるグラフは奇閉路を持たない
- 与えられるグラフは多重辺を持たない
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N M U_1 V_1 U_2 V_2 \vdots U_M V_M
出力
先手の青木君が勝つならば Aoki、後手の高橋君が勝つならば Takahashi と出力せよ。
入力例 1
4 3 1 2 2 3 3 4
出力例 1
Aoki
先手の青木君が (1,4) を選んで辺を追加すると、後手の高橋君は操作を行うことができません。よって青木君が勝ちます。
入力例 2
4 2 1 2 3 4
出力例 2
Takahashi
青木君がどのように操作を行っても、高橋君が勝ちます。
入力例 3
9 5 2 9 2 3 4 6 5 7 1 8
出力例 3
Aoki
Score : 600 points
Problem Statement
You are given a simple undirected graph with N vertices and M edges, with vertices labeled 1 to N and edges labeled 1 to M. The i-th edge connects vertices U_i and V_i. Initially, G does not contain an odd cycle.
Takahashi and Aoki will play a game using this graph G. With Aoki going first, they take turns performing the following operation:
- Choose a pair of integers (i,j) with 1 \leq i < j \leq N that satisfies both of the following conditions, then add an edge connecting vertices i and j to G.
- G does not already have an edge connecting vertices i and j.
- Adding an edge connecting vertices i and j does not create an odd cycle.
A player who cannot perform this operation loses, and the other player wins.
Determine who wins when both players play optimally.
What is an odd cycle?
A sequence of vertices (v_0,v_1,\ldots,v_k) of G is called an odd cycle if and only if all of the following conditions are satisfied:
- k is odd.
- v_0=v_k.
- For every 1\leq i \leq k, there is an edge connecting v_{i-1} and v_{i}.
Constraints
- 1 \leq N \leq 2\times 10^5
- 0 \leq M \leq 2\times 10^5
- 1 \leq U_i < V_i \leq N
- The given graph does not contain an odd cycle.
- The given graph does not contain multi-edges.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M U_1 V_1 U_2 V_2 \vdots U_M V_M
Output
If Aoki (the first player) wins, print Aoki; otherwise, if Takahashi (the second player) wins, print Takahashi.
Sample Input 1
4 3 1 2 2 3 3 4
Sample Output 1
Aoki
If Aoki (the first player) adds the edge (1,4), Takahashi (the second player) cannot move. Thus, Aoki wins.
Sample Input 2
4 2 1 2 3 4
Sample Output 2
Takahashi
No matter how Aoki plays, Takahashi wins.
Sample Input 3
9 5 2 9 2 3 4 6 5 7 1 8
Sample Output 3
Aoki