问题 1459. -- 抢键盘高手

1459: 抢键盘高手

时间限制: 1 Sec  内存限制: 128 MB
提交: 26  解决: 16
[提交][状态][讨论版]

题目描述

小Q和小W打比赛的时候总是抢键盘,小H为此非常苦恼。于是小H想了一个办法,就是让小Q和小W抢键盘的时候用游戏决胜负,赢了的人就有资格用键盘。游戏的规则是:由小H给出一个无向联通图,由小Q先手,两人轮流进行操作,每次必须从当前的图中删去一条边。如果某人执行操作之后,图变得不联通了,则该人判为失败。小H给出一个图,请你预测一下谁会赢。

输入

第一行输入两个正整数n(2 <= n <= 1e5),m(1 <= m <= 2e5),表示无向联通图的点数和边数。 接下来m行,每行两个数字a,b(1 <= a,b <= n),表示点a,b之间有一条边。

输出

输出一行,如果小Q赢,请输出“QKOQKO?QKOQKO!”(不含引号),如果小W赢,请输出“XDDYSJJGWWJY!”(不含引号)。

样例输入

4 5
1 2
2 3
3 4
4 1
2 3

样例输出

XDDYSJJGWWJY!

提示

来源

[提交][状态][讨论版]