Description

Kasra 和 Arshia 最近经常一起通勤，Arshia 把他带坏了。他们开车...

等等，等等...为什么故事这么长？

我们有一个有向图，需要从中选择一系列简单有向环，要求：

1. 每个顶点最多出现在一个环中
2. 可以从图中的某个节点出发，依次经过这些环。这意味着：
   • 可以从起始节点到达第一个环
   • 可以通过图中的边从一个环到达下一个环
   • 注意：在环间路径上经过的顶点不重要，允许在这些路径中多次访问某些顶点

现在我们需要知道有多少种选择这些环的方式。由于这个问题可能比较复杂，只需确定答案的奇偶性即可。

注意：

• 序列可以为空
• 两种选择方式不同当且仅当它们选择的环集合不同

Input Format

第一行包含两个整数 $n$ 和 $m$，分别表示图的顶点数和边数。

接下来 $m$ 行，每行给出图的一条边。

Output Format

如果答案的奇偶性是偶数，输出 Daddy: We should have a date...；如果是奇数，输出 Mistletoe: Time to go home!。

4 4
3 1
1 2
3 4
2 3

Daddy: We should have a date...

6 8
1 4
1 2
4 5
5 1
6 2
2 3
3 1
6 1

Mistletoe: Time to go home!

12 16
8 6
1 2
7 8
10 11
1 4
4 5
11 12
5 1
1 6
12 10
2 3
6 9
3 1
6 7
9 8
5 10

Daddy: We should have a date...

Hint

数据范围

• $1 \leq n \leq 5000$
• $0 \leq m \leq \min \left(\binom{n}{2},10^6\right)$
• $1 \leq u_{i}, v_{i} \leq n$

子任务

${}^1$: 仙人掌图是指任意两个环最多有一个公共顶点的无向图。

翻译由 DeepSeek V3 完成