T268089 xお嬢様は私に告白して欲しい

# 温馨提示：题目背景与题目内容无关。请先阅读简要题意。 感谢 [Brilliance_Z](https://www.luogu.com.cn/user/557756) 一起提供题目的 $idea$ 以及造数据。感谢 [IceAge](https://www.luogu.com.cn/user/167990) 帮忙买的一瓶可乐。 ------------ > $ {\color{9D3DCF}\mathcal{Love\ is\ war, Love\ is\ war,Love\ is\ war.}}$ $ xcx $ 和 $ cx $ ，两个字符串互相包含着彼此。 命中注定地， $ cx $ 和 $ xcx $ 是很好很好的好朋友。  $ cx $ 生日时， $ cx $ 也是这样问 $ xcx $ 的：  $ xcx $ ：你想要什么都可以哦～  $ xcx $ ：私がくれるものなら. It was **a moment in the life that cx can't forget**. $ cx $ ：我的愿望就是——就是——  It was the begin of all.

### 原始题意 今天是 $cx$ 的生日， $xcx$ 和 $cx$ 一起去玩娃娃机。 $n$ 个娃娃在娃娃机成一行排列。玩一次娃娃机需要花费 $1$ 单位的费用。由于 $cx$ 抓娃娃的技术比较菜， $cx$ 只能按照某种 **矩阵乘法** 的规律（规律详见简要题意）抓取娃娃。 这时， $xcx$ 说：“你能让我抓最后一个娃娃吗？” 此时心花怒放的 $cx$ 怎么可能不答应 $xcx$ 的请求呢？ 给定 $n$ 和 $cx$ 抓取娃娃的规律，请问 $cx$ 是否可以满足 $xcx$ 的请求？如果可以， $cx$ 至少需要花费多少单位费用？（**注意：费用只需计算到 $cx$ 抓到只剩最后一个娃娃为止， 轮到 $xcx$ 抓最后一个娃娃的费用不计算**） ### 简要题意 初始矩阵大小为 $1\times n$ ，且矩阵元素全为 $1$ 。 给定 $n$ 的大小以及一个 $n\times n$ 的 $01$ 矩阵。 求是否可以将初始矩阵乘上若干个的给定矩阵，使得**最终的初始矩阵有且仅有一个元素非 $0$** 。若可以，输出 `Let's play` 以及最小的矩阵幂次；反之，输出 `Poor cx` 。

第一行输入两个正整数 $n$ 和 $m$ 。 $n$ 的含义见简要题意， $m$ 的含义见下文。 接下来 $m$ 行，每行输入两个正整数 $x$ 和 $y$ ，表示给定矩阵的第 $x$ 行第 $y$ 列为 $1$ 。其他位置的矩阵元素为 $0$ 。

第一行输出 `Let's play` 或 `Poor cx` 。 若第一行为 `Let's play` ，第二行输出最小非负幂次。

### 样例解释 #### 样例组 #1 初始矩阵为 $\begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix}$ 。 给定矩阵为 $\begin{bmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 \end{bmatrix}$ 。 第一次相乘： $\begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix}\times\begin{bmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 \end{bmatrix}=\begin{bmatrix} 0 & 1 & 1 & 1 \end{bmatrix}$ 此时还有 $3$ 个位置的元素非 $0$ 。 第二次相乘： $\begin{bmatrix} 0 & 1 & 1 & 1 \end{bmatrix}\times\begin{bmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 \end{bmatrix}=\begin{bmatrix} 0 & 0 & 0 & 1 \end{bmatrix}$ 此时还有 $1$ 个位置的元素非 $0$ ，满足要求。因此最小幂次是 $2$ 。 #### 样例组 #2 初始矩阵为 $\begin{bmatrix} 1 & 1 & 1 \end{bmatrix}$ 。 给定矩阵为 $\begin{bmatrix} 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}$ 。 第一次相乘： $\begin{bmatrix} 1 & 1 & 1 \end{bmatrix}\times\begin{bmatrix} 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}=\begin{bmatrix} 0 & 1 & 1 \end{bmatrix}$ 此时还有 $2$ 个位置的元素非 $0$ 。 第二次相乘： $\begin{bmatrix} 0 & 1 & 1 \end{bmatrix}\times\begin{bmatrix} 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}=\begin{bmatrix} 0 & 0 & 0 \end{bmatrix}$ 此时有 $0$ 个位置的元素非 $0$ ，可以证明无法满足要求。 ### 数据范围 **本题采用捆绑测试。你只有通过一个子任务内所有的测试点，才能获得该子任务的分数。** > 因此，你全部输出 `Poor cx` 可以获得~~0分的好成绩~~。 | 子任务编号 | $n\leqslant $ | 是否保证 $A$ | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | 是 | | $20$ | | $2$ | $10$ | 是 | $B$ | $10$ | | $3$ | $150$ | 是 | | $20$ | | $4$ | $5\times10^3$ | 是 | | $10$ | | $5$ | $5\times10^3$ | 是 | $C$ | $10$ | | $6$ | $2\times10^5$ | 是 | | $10$ | | $7$ | $2\times10^5$ | 是 | $D$ | $10$ | | $8$ | $2\times10^6$ | 否 | | $10$ | $A$：给定的数对 $(x,y)$ 中 $x\ne y$。 $B$：给定矩阵的元素全为 $1$ 。 $C$：数据随机且该子任务只有一个测试点。 $D$： $m\le 10$。 对于 $100\%$ 的数据，保证 $1 \le n \le 2\times10^6$ ， $0\le m \le \min(2\times10^6,n^2)$ 。不保证给定的数对 $(x,y)$ 不重复。