這天,喵喵國長出了一些神秘的樹,
因為它們長得很快,霎時間就樹姿雄偉,高大挺拔,
簡單來說就是長得很胖(?),於是被喵喵國人民稱為胖胖樹。
這種樹長得很奇怪,它會到處亂長,
然後可怕的是,由於它長太快了,自己的某些枝條會插上自己的某些枝條,也就是他的樹枝會合併。
有一天,喵喵國出現了兩位神秘的人物,胖胖蚯和胖胖蝶,
他們是傳說中在IOI打敗tourist的大神,最近來到喵喵國觀光。
他們看到了這棵樹以後,覺得非常漂亮,想要把這棵樹畫下來,
不過這棵樹實在長得太複雜了,於是他們就講這棵樹的結構稍微簡化,只紀錄分支點,和分支點相連的情形,
簡單來說就是弄成了一張無向+maybe有環圖,(其實就是一般的圖?)
還好這棵樹稍微有點智慧,不會把樹枝插到地上,所以跟地面接觸的點只會有樹根,而這個點會被紀錄為編號1的點。
把圖畫完以後,胖胖蚯和胖胖蝶感到十分無聊,
由於最近他們都在Tetris Battle,免不了想要打架。
因Battle而黑化的兩人十分邪惡,
所以他們想要來支解這些樹。
首先由胖胖蝶開始(因為胖胖蝶很糟糕,所以騙到了先手),
兩個人輪流在這張圖上輪流砍掉一條邊,
如果當砍掉某條邊時,某些點連不到樹根了,那些點就會從樹上掉落,
接著這些點就會被無視,並移出遊戲外。
如果沒有邊可以砍的人就輸掉了。
兩位大神要battle的消息很快的在喵喵國的人民傳開了,引來了大家的圍觀,
也請來了喵喵國的國王,god shik來當裁判,
由於樹很多,且胖胖蝶和胖胖蚯對於每一棵樹,他們都會Battle一次,
可是god shik十分想睡覺,他不想等到兩人把每一場都打完。
祂知道這兩個人都十分聰明,如果能贏就一定會贏。
於是祂想要在比賽開始前就先判定好每一場比賽是誰會贏,或是平手。
如此祂就能提早回去睡覺。
由於想睡覺的時候無法思考,所以god shik要請你幫忙計算每一場battle的結果會是如何。
輸入會有很多棵樹,保證樹的數量 <= 50。讀到EOF結束。
對於每一棵樹首先會有兩個整數N, M,分別表示這棵樹的分支點數量和枝條的數目。 (1 <= N <= 80000, N-1 <= M <= 120000)
之後會有M行,每行有兩個正整數A, B,表示這根樹枝連接編號為A和編號為B的分支點。
保證一開始每根樹枝都在樹上,也就是每個分支點都可以被連到樹根。
對於每一棵樹,輸出會獲勝的人是胖胖蚯還是胖胖蝶,
如果是胖胖蝶獲勝,輸出
DarkBtf
如果是胖胖蚯獲勝,輸出
DarkWorm
如果兩人會平手,則輸出
Even
8 7 1 2 1 3 3 4 1 5 5 6 6 7 7 8
DarkBtf
Migrated from old NTUJ.
余孟桓 TOI 2011
No. | Testdata Range | Score |
---|