Problem4655--n 子棋

4655: n 子棋

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

小 A 和小 B 在玩 nnn 子棋, nnn 子棋游戏的规则是,两人在一个左上角是 (1,1)(1,1)(1,1),右下角是 (n,n)(n,n)(n,n)n×nn \times nn×n 棋盘中交替落子,只要有一方的 nnn 个棋子在同一行或者同一列或者同一条对角线上,对方就输了。
游戏由小 A 先手,一共进行了 mmm 回合,请你来当裁判,帮他们裁定胜负。
游戏结束的条件是:
  • 出现胜负;
  • 所有回合结束。
一旦满足上述任意一个条件,游戏立即结束,后续回合无效。

Input

第一行两个整数 n,mn,mn,m ,表示棋盘大小和回合数。
接下来 mmm 行,每行两个数 x,yx,yx,y,表示当前轮到的人会在第 xxx 行第 yyy 列放一个棋子。

Output

输出一行,包含一个整数 xxx ,表示游戏结束的回合,和一个字符串 SSS 表示游戏结果,用一个空格隔开。
若小 A 赢了 SSS 为"milk!";小 B 赢了 SSS 为"juice!";否则 SSS 为"drawn!"。

Sample 1 Input

2 4
1 1
2 2
2 1
1 2

Sample 1 Output

3 milk!

HINT

【数据规模】
对于前 10%10\%10% 的数据,保证 n=1n=1n=1
对于前 30%30\%30% 的数据,保证 1≤n≤21\leq n \leq 21n2
对于前 70%70\%70% 的数据,保证 1≤n≤501\leq n \leq 501n50
对于前 90%90\%90% 的数据,保证 1≤n≤5001\leq n\leq 5001n500
对于 100%100\%100% 的数据,保证 1≤n≤105,0≤m≤min⁡(3×105,n2)1\leq n\leq 10^5, 0\leq m \leq \min(3\times 10^5, n^2)1n105,0mmin(3×105,n2)

Source/Category