Background

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

Problem 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