You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

一位年过古稀的老爷爷在乡间行走。

而他不想兜圈子，因为那会使他昏沉。

偶然路过小 A 发扬助人为乐优良传统，带上地图，想知道路况是否一定使他清醒。

usqwedf 补充：为了让欢乐赛充满欢乐，小 A 还想问你一些数学作业……

题目描述

任务 1

给定一张 $n$ 个点 $m$ 条边的有向图，判断图中是否没有环。

任务 2.1

给定一个整数 $k$，求 $2^k \bmod 9997$ 的值。

任务 2.2

给定一个整数 $k$，求 $k^2$ 的值，答案不需要取模。

输入格式

第一行三个整数 $n,m,k$。

下面 $m$ 行，每行两个正整数 $u,v$，表示一条有向边 $u \to v$。

输出格式

任务 1

如果确实没有环（没有环），输出一行一个字符串 Yes。

如果并非没有环（有环），输出一行一个字符串 No。

任务 2.1

如果任务 1 的答案为 No，则忽略这个任务，什么也不输出。

如果任务 1 的答案为 Yes，则（在输出任务 1 的答案后）输出一行一个整数表示答案。

任务 2.2

如果任务 1 的答案为 Yes，则忽略这个任务，什么也不输出。

如果任务 1 的答案为 No，则（在输出任务 1 的答案后）输出一行一个整数表示答案。

3 3 3
1 2
2 3
3 1

No
9

提示

对于 $70\%$ 的数据，$1 \le n \le 100$，$1 \le m \le 1000$，$1 \le k \le 30$。

对于 $100\%$ 的数据，$1 \le n \le 1000$，$1 \le m \le 10000$，$1 \le k \le 10^9$。

特别地，对于其中至少 $20\%$ 的数据，任务 1 的答案为 No。