Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Last Game of Onslaught

By Tash52 · 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

    Discussion

    Statistics


    75% Solution Ratio

    pathanEarliest, 3w ago

    alamkhanFastest, 0.2s

    NirjhorLightest, 17 MB

    YouKnowWhoShortest, 861B

    Submit

    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.