P1992 An Old Man Who Doesn't Want to Walk in Circles

An elderly man in his seventies is walking through the countryside. He does not want to walk in circles, because that would make him dizzy. Happening to pass by, Xiao A, upholding the fine tradition of helping others, brings a map and wants to know whether the road conditions will certainly keep the old man clear‑headed. usqwedf added: To make the fun contest truly fun, Xiao A would also like to ask you some math homework...

#### Task 1 Given a directed graph with $n$ vertices and $m$ edges, determine whether the graph has no cycles. #### Task 2.1 Given an integer $k$, compute $2^k \bmod 9997$. #### Task 2.2 Given an integer $k$, compute $k^2$, and the answer does not need to be taken modulo anything.

The first line contains three integers $n, m, k$. The next $m$ lines each contain two positive integers $u, v$, indicating a directed edge $u \to v$.

#### Task 1 If there are indeed no cycles (no cycles), output one line containing the string **`Yes`**. If it is not the case that there are no cycles (there is a cycle), output one line containing the string **`No`**. #### Task 2.1 If the answer to Task 1 is **`No`**, then ignore this task and output nothing. If the answer to Task 1 is **`Yes`**, then (after outputting the answer to Task 1) output one line containing an integer for the answer. #### Task 2.2 If the answer to Task 1 is **`Yes`**, then ignore this task and output nothing. If the answer to Task 1 is **`No`**, then (after outputting the answer to Task 1) output one line containing an integer for the answer.

For 70% of the testdata, $1 \le n \le 100$, $1 \le m \le 1000$, $1 \le k \le 30$. For 100% of the testdata, $1 \le n \le 1000$, $1 \le m \le 10000$, $1 \le k \le 10^9$. In particular, for at least 20% of the testdata, the answer to Task 1 is `No`. Translated by ChatGPT 5