Last Game of Onslaught

Tash52 Intra AUST Programming Co...
Limits 1s, 512 MB

Tashfiq and Alam have been on the same team for almost two years. Tashfiq often comes up with some ridiculous games that they both play. Tashfiq will retire next year. So he invited Alam to one last game. Akash bhai is joining to watch over the game as a referee. Alam is determined to win this one at all costs. But he thinks there may be some way to determine the winner of each game. He is asking you for help.

At first, Akash bhai creates an undirected connected graph with N nodes and M edges. There are no self-loops and no edge is repeated more than once. Now he applies Q operations on the graph. X is the starting node for every operation. Akash bhai will choose a number Y in each operation. He will create a pile of mangoes ( guess why!! ) with the same number of mangoes as the length of the shortest path from X to Y and he will do so for each of the Q operations.

Now the game begins.

Tashfiq and Alam will have to finish these mangoes. They are both renowned as heavy eaters. But they have to take some rest. Alam will go first. He will eat a number of mangoes and take some rest. Then Tashfiq will make a move for the mangoes and take rest after eating some. This will keep going until all the mangoes are finished. A player has to eat at least one mango before they can take rest. They will not eat at the same time, nor will they eat from multiple piles after starting to eat. If the pile empties while eating that player will go to rest. Both players will play optimally.

Akash bhai has to keep an eye on them so that they don’t fall sick. So he declared one ridiculous rule, the person to eat the last mango will lose. But a game is a game.

Input

The first line will contain integers N, M, X, and Q. Each of the next M lines will contain two integers, U and V, denoting there is an edge between node U and V. ( U != V)
Each of the next Q lines will contain a single integer Y as described in the statement.

1<=N <=100000

N-1 <= M <= min(1000000,N*(N-1)/2)

1<=X,Y<=N

1<= Q <= 100000

Output

For each of the Q sets output a single line with the name of the winner. If Tashfiq wins print “Tashfiq“ and if Alam wins print “Alam“ without the quotes.

Sample

InputOutput
6 6 1 3
2 1
1 5
4 1
5 4
2 6
3 6
5
3
6
Tashfiq

Submit

Login to submit.

Statistics

75% Solution Ratio
pathanEarliest, 11M ago
alamkhanFastest, 0.2s
NirjhorLightest, 17 MB
YouKnowWhoShortest, 861B
Toph uses cookies. By continuing you agree to our Cookie Policy.