Dependency Flood (Problem D, CS3233 Midterm Contest 2025, 2025)
Time limit: 2 sec
Memory limit: 1024 MB

# Problem Statement

A university offers $N$ courses, numbered from $1$ to $N$ in increasing order of difficulty.

To ensure that students acquire the necessary knowledge before taking advanced courses, the university may impose **course dependencies**. Each course dependency is represented by a pair of integers $(u, v)\ (1 \le u < v \le N)$, meaning that students must complete course $u$ before enrolling in course $v$.

A set of course dependencies is called **acceptable** if all $N$ courses can be completed within $K$ semesters, assuming that a student can take any number of courses (possibly zero) in a semester.

Formally, a set of course dependencies is acceptable if and only if there exists a sequence of $N$ numbers $a_1, a_2, \ldots, a_N\ (1 \le a_i \le K)$ such that $a_u < a_v$ for every $(u, v)$ in the set.

Let $S$ be the set of course dependencies. Initially, $S$ consists of $M$ course dependencies $(A_1, B_1), (A_2, B_2), \ldots, (A_M, B_M)$, and **it is guaranteed that $S$ is acceptable.**

You need to process $Q$ queries sequentially. The $i$-th query $(1 \le i \le Q)$ is as follows:

- Given two integers $C_i, D_i\ (1 \le C_i < D_i \le N)$, determine whether adding a new dependency $(C_i, D_i)$ to $S$ maintains its acceptability. If adding this dependency makes $S$ unacceptable, output **reject** and leave $S$ unchanged. Otherwise, output **accept** and add $(C_i, D_i)$ to $S$.

# Input

The first line of input contains three integers $N,\ M$ and $K\ (2 \le N \le 2 \times 10^5,\ 0 \le M \le 2 \times 10^5,\ 1 \le K \le 100)$, representing the number of courses, the number of initial course dependencies, and the number of semesters, respectively.

The $i$-th line $(1 \le i \le M)$ of the next $M$ lines contain two integers $A_i$ and $B_i\ (1 \le A_i < B_i \le N)$, denoting the $i$-th initial course dependency.

The following line contains an integer $Q\ (1 \le Q \le 2 \times 10^5)$, the number of queries.

The $i$-th line $(1 \le i \le Q)$ of the next $Q$ lines contain two integers $C_i$ and $D_i\ (1 \le C_i < D_i \le N)$, representing the $i$-th query.

# Output

Output $Q$ lines.

The $i$-th line $(1 \le i \le Q)$ of the output should contain the result for the $i$-th query: Print **accept** if adding the dependency $(C_i, D_i)$ keeps $S$ acceptable, or **reject** if it makes $S$ unacceptable.

# Sample Input #1
```
4 1 2
1 2
3
2 3
3 4
1 3
```
# Sample Output #1
```
reject
accept
reject
```
# Sample Input #2
```
6 4 3
2 5
1 3
1 4
4 6
8
2 6
3 4
4 5
1 3
2 4
3 6
2 3
5 6
```
# Sample Output #2
```
accept
reject
accept
accept
accept
accept
accept
reject
```

Sample inputs:
4 1 2
1 2
3
2 3
3 4
1 3

6 4 3
2 5
1 3
1 4
4 6
8
2 6
3 4
4 5
1 3
2 4
3 6
2 3
5 6

Sample outputs:
reject
accept
reject

accept
reject
accept
accept
accept
accept
accept
reject

# Solution Analysis

For simplicity, we will use graph theory terminology instead of the definitions given in the problem statement. Note that acceptability is equivalent to ensuring that there is no path of length $K$.

Let $f_i$ ($1 \leq i \leq N$) be the maximum path length ending at vertex $i$, and let $b_i$ ($1 \leq i \leq N$) be the maximum path length starting from vertex $i$. The values of $f_i$ satisfy the following recurrence relation, where $E$ denotes the set of edges:

$$
f_i = \left\{
\begin{array}{ll}
1 + \max_{(j, i) \in E} f_j & \exists (j, i) \in E \\
0 & \text{otherwise}
\end{array}
\right.
$$

Thus, the initial values of $f_i$ can be computed in $\mathcal{O}(N + M)$ time by processing vertices in ascending order. Similarly, the initial values of $b_i$ can be computed in descending order.

If we can efficiently maintain the values of $f_i$ and $b_i$, checking whether a new edge can be added becomes straightforward using the following lemma:

**Lemma.** *A new edge $(u, v)$ can be added if and only if $f_u + b_v + 1 < K$.*

**Proof.** Exercise.

The key challenge is efficiently updating $f_i$ and $b_i$ when a new edge $(u, v)$ is added. We describe the update process for $f_i$ (the update for $b_i$ follows analogously).

Given the way $f_i$ is initially computed, we can derive an update algorithm using a simple DFS, as shown in the following pseudocode:

```python
Function update(i, val):
    f[i] = val
    for each edge (i, j):
        if f[j] < f[i] + 1:
            update(j, f[i] + 1)

Function add_new_edge(u, v):
    if f[v] < f[u] + 1:
        update(v, f[u] + 1)
```

This recursive algorithm appears to require $\mathcal{O}(N + M)$ time per edge addition, leading to a total complexity of $\mathcal{O}(Q(N + M))$. However, we observe that the function update is called at most $(K - 1)N$ times in total. This is because:

- Every call of the function increases some $f_i$ by at least one

- The sum of all $f_i$ values never exceeds $(K - 1) \times N$, as the problem requires $f_i \leq K - 1$ to hold for any $i$ at all times

- The values of $f_i$ never decrease

Hence we can solve this problem in the overall time complexity of $\mathcal{O}(Q + K(N + M))$.



Special judge (C++ scorer):