Hide

Problem D
Dependency Flood

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\leq u < v\leq 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, \dots , a_N$ ($1\leq a_i\leq 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), \dots , (A_M, B_M)$, and it is guaranteed that $S$ is acceptable.

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

  • Given two integers $C_i, D_i$ ($1\leq C_i < D_i\leq 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 \leq N \leq 2\times 10^5$, $0 \leq M \leq 2\times 10^5$, $1\leq K\leq 100$), representing the number of courses, the number of initial course dependencies, and the number of semesters, respectively.

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

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

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

Output

Output $Q$ lines.

The $i$-th line ($1\leq i\leq 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 Sample Output 1
4 1 2
1 2
3
2 3
3 4
1 3
reject
accept
reject
Sample Input 2 Sample Output 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
accept
reject
accept
accept
accept
accept
accept
reject

Please log in to submit a solution to this problem

Log in