Description

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.

Input Format

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$.

Output Format

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.

3 3 3
1 2
2 3
3 1

No
9

Hint

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