{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e Read problems statements in \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/APRIL14/mandarin/GERALD08.pdf\"\u003eMandarin Chinese \u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/APRIL14/russian/GERALD08.pdf\"\u003eRussian\u003c/a\u003e.\u003c/h3\u003e\r\n\r\n\u003cp\u003e \u003c/p\u003e\r\n\u003cp\u003eChef has a rooted tree \u003cb\u003eG\u003c/b\u003e, consisting of \u003cb\u003eN\u003c/b\u003e vertices. Each edge of the tree has a color black or white.\u003c/p\u003e\r\n\u003cp\u003eOnce Chef\u0027s friend Ksen offered Chef to play a game on the tree \u003cb\u003eG\u003c/b\u003e. The game has very simple rule:\r\n\u003cul\u003e\r\n\u003cli\u003eThe players make moves in the game alternately.\u003c/li\u003e\r\n\u003cli\u003eOn his move Chef deletes a single undeleted black edge. On her move Ksen deletes a single undeleted white edge.\u003c/li\u003e\r\n\u003cli\u003eWhen some edge has been deleted, all the edges that now aren\u0027t connected (directly or indirectly) to the root will be deleted too.\u003c/li\u003e\r\n\u003cli\u003eOne who cannot move lose the game.\u003c/li\u003e\r\n\u003c/ul\u003e\u003c/p\u003e\r\n\u003cp\u003eChef really likes the game. The only problem is that Ksen knows the game very well. So she always plays optimally. That\u0027s why Chef has decided to choose the order of moves. Help Chef: tell him who will win the game if he moves first, and also who will win the game if Ksen moves first. Consider that Chef plays optimally too.\u003c/p\u003e\r\n\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe first line of the input contains an integer \u003cb\u003eT\u003c/b\u003e denoting the number of test cases. The description of \u003cb\u003eT\u003c/b\u003e test cases follows.\u003c/p\u003e\r\n\u003cp\u003eThe first line of each testcase contains a single integer \u003cb\u003eN\u003c/b\u003e. Then \u003cb\u003eN - 1\u003c/b\u003e lines follows. Each contains three integers \u003cb\u003eU\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eV\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eC\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e. These integers denotes the current edge of the tree: the first two numbers means the numbers of vertices connected by the edge, the last number denotes the color of the edge (zero means black, one means white). Consider all vertices of the tree \u003cb\u003eG\u003c/b\u003e are numbered from \u003cb\u003e1\u003c/b\u003e to \u003cb\u003eN\u003c/b\u003e. The root has number \u003cb\u003e1\u003c/b\u003e.\u003c/p\u003e\r\n\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each test case, output a single line containing two strings: the name of the winner if Chef moves first, and the name of the winner if Chef moves second.\u003c/p\u003e\r\n\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eT\u003c/b\u003e ≤ \u003cb\u003e1000\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e ≤ \u003cb\u003e100000\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eU\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eV\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e0\u003c/b\u003e ≤ \u003cb\u003eC\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003e1\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003eIt\u0027s guaranteed that the sum of \u003cb\u003eN\u003c/b\u003e values for all tests doesn\u0027t exceed 100000.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003cbr\u003e\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cpre\u003e\u003cb\u003eInput:\u003c/b\u003e\r\n5\r\n1\r\n2\r\n1 2 0\r\n2\r\n1 2 1\r\n3\r\n1 2 0\r\n1 3 1\r\n3\r\n1 2 0\r\n2 3 1\r\n\r\n\u003cb\u003eOutput:\u003c/b\u003e\r\nKsen Chef\r\nChef Chef\r\nKsen Ksen\r\nKsen Chef\r\nChef Chef\r\n\u003c/pre\u003e\r\n\u003cp\u003e \u003c/p\u003e\r\n"}}]}