Naruto and Sasuke

All submissions for this problem are available.
Naruto and Sasuke were bored of playing conventional games to get rid of rivalry. Their wives Hinata and Sakura respectively presented them with various games but all left them cold.
So, they (Hinata and Sakura) decided to create a new game...
They defined Game G, with following tuples:
S: Set of all possible states that the game could be in.
W: Set of winning states (Subset of S).
M: Set of moves. Each move is given by an unordered pair(A, B), where A & B belong to S, defines the valid transition between two states A and B i.e. a player can make a single move to transform the game from state A to state B and viceversa.
G can be transformed from a nonwinning state (a state in SW i.e. the set of all possible states that are in S but not in W) to a winning state (a state in W) by applying a sequence of moves.
And in this process the player making the last move wins.
Legal moves are those which can be used in the sequence of moves while transforming G from a nonwinning state to a winning state.
Illegal moves are those which can never be used for transforming G from nonwinning state to winning state.
For example, consider G: where S={1,2,3,4,5} , W={1}, M={(1,2),(2,3),(1,3),(4,5)}
Here (1,2), (2,3) and (1,3) are legal moves as they can be used in transforming G from states 2 and 3 to state 1 as follows : 2>1 or 2>3>1 or 3>1.
However (4,5) is illegal as it can never be used for transforming G from any state to 1.
The game can start at any of nonwinning state(any state in SW).
But when this game is presented to Naruto and Sasuke, instead of playing it, they thought that there are too many moves and hence it will only be a waste of time playing this game.
So they decided to add restrictions to the move set.
A restriction is made by banning a legal move i.e. they can pick a legal move from M and remove it from M.
Note: Imposing restriction may cause some other move to become illegal.
For example, consider G, where S={1,2,3,4,5} , W={1}, M={(1,2),(2,3),(4,5)}
Initially (2,3) is legal but once (1,2) is removed then (2,3) becomes illegal.
Also, note that they can't remove (4,5) as it's already illegal.
Restrictions are imposed in the following way :
 Both Naruto and Sasuke take chance alternating, starting with Naruto.
 In each chance, they impose a restriction of their choice.
Eventually, they found out that they can make G a NO WINNER game, i.e. a game in which no player is able to win the game irrespective of any starting state (G can never be transformed from a state in SW to a state in W with remaining moves in M). In other words, G is a NO WINNER game if M does not contain any legal move. They found it interesting and suddenly developed a race to make G a NO WINNER game. The first person to make G a NO WINNER game wins the race. But they got so carried away that their wives are now worried.
The only way to end this race is that you predetermine the winner of the race. Can you help them in this task ?
Input
The first line of input contains a single integer T denoting the number of test cases. The description of T test cases follow. Each describes a scenario for G through S, W, and M.
The first line contains two space separated integers P and Q denoting the total number of possible states (cardinality of S) and the total number of moves (cardinality of M) respectively.
(The elements in S are numbered from 1 to P)
Each of the next Q lines contain two spaceseparated integers A and B describing a possible move from state A to state B and viceversa (i.e. (A,B) belongs to the set M)
Next line contains single integer R denoting the number of winning states (cardinality of W).
The last line contains R spaceseparated integers representing the elements of W.
Note
You can assume that there is no move between two winning states, or formally, there is no element (A,B) present in M such that both A and B belong to W.
All the moves in M are unique and define transitions between two different states.
Output
For each test case (i.e. each game), you have to determine the winner of the race considering that both of Naruto and Sasuke play optimally. If Naruto wins, then you have to print 'naruto' without quotes and if Sasuke wins, then you have to print 'sasuke' without quotes. For each test case print the answer on a new line.
Constraints
 1 ≤ T ≤ 50
 2 ≤ P ≤ 10^{5}
 1 ≤ Q ≤ 10^{5}
 1 ≤ A,B ≤ P
 1 ≤ R < P
Information to Score Partial Points
 For 20% of the score, it is guaranteed that P ≤ 10, Q ≤ 15.
 For the rest of the 80% of the score, no extra guarantees.
Example
Input:
3
4 3
1 2
2 3
3 4
1
1
3 2
1 2
1 3
1
1
4 4
1 3
2 3
3 4
2 4
2
1 2
Output: naruto
sasuke
sasuke
Explanation
Example case 1. In the first test case, we have SW = {2,3,4} and M={(1,2), (2,3), (3,4)}. So the game G can start with states 2 or 3 or 4. If Naruto removes (1,2) from M, then clearly no player can win G irrespective of whether the G starts with states 2 or 3 or 4, as this is the only move to reach winning state 1.Hence this move makes G  a NO WINNER game and Naruto wins the race.
In the second test case, we have SW = {2,3} and M={(1,2), (1,3)}. So the game G can start with states 2 or 3. If Naruto removes (1,2) first, then M becomes {(1,3)}. Now, no player wins if G starts with 2, but if G starts with 3, then a player can make a move (1,3), to transform G from state 3 to state 1 and hence winning the game, thus G is currently not a NO WINNER game. Hence Sasuke takes next chance and removes (1,3) making M={}, hence there are no moves to take in G and thus if G start in SW, it can never be transformed to a state in W(as there are no moves to take), thus G becomes NO WINNER game. Hence Sasuke wins the race. A similar analysis applies if Naruto removes (1,3) first from M.
Author:  mohitbindal644 
Tags  mohitbindal644 
Date Added:  17022018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions