Chef and Tree Game
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef has a rooted tree G, consisting of N vertices. Each edge of the tree has a color black or white.
Once Chef's friend Ksen offered Chef to play a game on the tree G. The game has very simple rule:
- The players make moves in the game alternately.
- On his move Chef deletes a single undeleted black edge. On her move Ksen deletes a single undeleted white edge.
- When some edge has been deleted, all the edges that now aren't connected (directly or indirectly) to the root will be deleted too.
- One who cannot move lose the game.
Chef really likes the game. The only problem is that Ksen knows the game very well. So she always plays optimally. That's 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.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each testcase contains a single integer N. Then N - 1 lines follows. Each contains three integers Ui, Vi, Ci. 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 G are numbered from 1 to N. The root has number 1.
For 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.
- 1 ≤ T ≤ 1000
- 1 ≤ N ≤ 100000
- 1 ≤ Ui, Vi ≤ N
- 0 ≤ Ci ≤ 1
- It's guaranteed that the sum of N values for all tests doesn't exceed 100000.
Input: 5 1 2 1 2 0 2 1 2 1 3 1 2 0 1 3 1 3 1 2 0 2 3 1 Output: Ksen Chef Chef Chef Ksen Ksen Ksen Chef Chef Chef
|Tags||april14, gerald, hackenbush, medium-hard|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.