Taran and Tarini
All submissions for this problem are available.In a far away Galaxy of Tilky Way, there was a planet Tarth where the sport of Tompetitive Toding was very popular. According to legends, there lived a very random setter known for his short and crispy problem statements. Often I ask, "What does a city truly look like?" - and the answer is obvious, it looks like a Graph with $N$ nodes connected by edges :). For sake of simplicity, let us further assume the city to be represented by a tree with $N-1$ edges. Now, it was a special day for Tarini, who was waiting for Taran at Node $X$. They were going to out and were about to have some fun :). But Taran didnt arrive there yet, so she had nothing much to do right now. Hence, in acccordance to the holy verdict of God, and as decreed by the basic fundamentals of human nature (especially feminine), she started to *think*. "What are the chances that I will *really* enjoy today?" Now, everybody knew (except you!) that there are great shops at Node $U$ from where Taran might bring Tarini lots and lots of gift, making her happy and enjoy the day. And now thinking about that, Tarini felt how miserable it'd be if Taran came empty handed! Also, Tarini knows that Taran is very lazy and frugal and he will buy gifts from shop only if it falls on his way to Tarini (because **WHO** would want to reach as soon as possible to his waiting girl friend and hence come by shortest path? Boys? Never!). Now, Tarini is very self-less and rational. Hence, logically she predicted how miserable and unhappy they'd be $60$ years from now on because Taran didn't bring him a gift. She must not let such miseries happen! So she decided, that if Taran wouldn't be bringing her the gift, better cancel the plans and go surf memes all day with her friend Sakub-Jafin (whose meme-game is immortal!) so that not only could she enjoy herself, but prevent all miseries she and Taran might face (even after $60$ years) because Taran didn't bring her a gift. Now, Tarini kind of forgot where the shop, and Taran were. Hence she will ask you $Q$ queries - each one will give $2$ nodes, $U$ (location of shop) and $V$ (location of Taran) and you mus tell her if she should spend the day with Taran, or Sakub-Jafin. Also, obviously, if the shop is also on Node $X$( i.e. where Tarini is) she will make Taran buy a gift and spend day with him :) *(PS: Looking at Taran's condition, Vijju was very very VERY happy about his loneliness and aloofness from the momentary ties of this perishable, illusionary world.)*
###Input: - First line will contain $T$, number of testcases. Then the testcases follow. - Each testcase the first line contains $3$ integers, $N$, $Q$ and $X$, i.e. Number of Nodes, Number of Queries and Location of Tarini. - Next $N-1$ lines will have $2$ integers describing the tree. In other words, each of these lines with have $2$ integers $U$ $V$ representing "There is an edge between Node $U$ and Node $V$". - Next $Q$ lines describe Tarini's queries. Each line with again ahve $2$ integers $A$ $B$, where $A$ is the node in which shop is located and $B$ is location of Taran.
###Output: For every query in each test case, output who she should spend the day with, i.e. output either `Taran` or `Sakub-Jafin` in EXACT same spelling.
###Constraints - $1 \leq T \leq 10$ - $1 \leq N,Q,X \leq 10^5$ - $1 \leq U,V,A,B \leq N$
###Subtasks **Sub-Task #1 - 20 points :** - $T=10$ - $1 \leq N,Q \leq 1000$ **Sub-Task #2 - 20 points :** - The given Graph is a Binary Tree of height $O(LogN)$. - $X=1$ **Sub-Task #3 - 20 Points :** - The given Graph is a linear chain. **Sub-Task #4 - 40 Points :** - Original Constraints.
###Sample Input: 1 3 2 1 1 2 1 3 2 3 2 2 ###Sample Output: Sakub-Jafin Taran
###EXPLANATION: Tarini is at Node $1$. In first query, Taran will go from Node $3$ to Node $1$ without going to Node $2$ where shop is located, and hence wont buy a gift. In next query, Taran and Shop both are at Node $2$, hence he will buy her a gift.
|Tags||easy, euler-tour, icop1902, taran_1407, vijju123|
|Time Limit:||2 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|
Fetching successful submissions