P12455 [INOI Team Selection 2021] Andarzgu

Kasra 和 Arshia 最近经常一起通勤，Arshia 把他带坏了。他们开车... 等等，等等...为什么故事这么长？ 我们有一个有向图，需要从中选择一系列简单有向环，要求： 1. 每个顶点最多出现在一个环中 2. 可以从图中的某个节点出发，依次经过这些环。这意味着： - 可以从起始节点到达第一个环 - 可以通过图中的边从一个环到达下一个环 - 注意：在环间路径上经过的顶点不重要，允许在这些路径中多次访问某些顶点 现在我们需要知道有多少种选择这些环的方式。由于这个问题可能比较复杂，只需确定答案的奇偶性即可。 注意： - 序列可以为空 - 两种选择方式不同当且仅当它们选择的环集合不同

第一行包含两个整数 $n$ 和 $m$，分别表示图的顶点数和边数。 接下来 $m$ 行，每行给出图的一条边。

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

### 数据范围 - $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 | 13 | 该无向基础图是仙人掌图${ }^{1}$ | | 2 | 36 | $1 \leq n \leq 500$，图是强连通的 | | 3 | 51 | 无额外限制 | ${}^1$: 仙人掌图是指任意两个环最多有一个公共顶点的无向图。 翻译由 DeepSeek V3 完成