For a graph $G$, define the following game:
The game is played between two sufficiently intelligent players, Alice and Bob. There is a token. Alice first chooses any node in $G$ and places the token on it. Then, Bob and Alice take turns moving the token along an edge in $G$ to any adjacent node that the token has not visited before. Bob moves first. The player who cannot make a move loses.
For an undirected graph $G$ with $n$ nodes and a positive integer $k$, the graph $G^k$ is defined as follows:
- $G^k$ contains $nk$ nodes, which are $(1, 1), (1, 2), \dots, (1, n), (2, 1), \dots, (2, n), \dots, (k, 1), \dots, (k, n)$.
- For all $i \in [1, k]$, there is an undirected edge between $(i, u)$ and $(i, v)$ if and only if there is an undirected edge between $u$ and $v$ in $G$.
- For all $i \in [1, k - 1]$ and $u \in [1, n]$, there is an undirected edge between $(i, u)$ and $(i + 1, u)$.
There is a forest with $n$ nodes, initially containing $m$ edges. There are $q$ operations of three types:
- $\texttt{1 u v}$: Add an undirected edge between $u$ and $v$. It is guaranteed that the graph remains a forest after the operation.
- $\texttt{2 u v}$: Remove the undirected edge between $u$ and $v$. It is guaranteed that an edge between $u$ and $v$ exists when this operation is performed.
- $\texttt{3 u k}$: Let $T$ be the tree in the forest containing $u$. Determine the result of the game described above played on $T^k$.
Input
The first line contains three non-negative integers $n, m, q$.
The next $m$ lines each contain two positive integers $u, v$, representing an edge between $u$ and $v$ in the initial forest.
The next $q$ lines each contain three positive integers representing an operation, in the format described above.
Output
For each type 3 operation, output a single line containing either $\texttt{Alice}$ or $\texttt{Bob}$, representing the winner of the game.
Examples
Input 1
6 4 5 1 3 2 3 4 5 4 6 3 1 114514 3 1 998244353 1 3 4 3 1 1 3 1 3
Output 1
Bob Alice Alice Bob
Constraints
This problem uses bundled testing. The subtask information is as follows:
| Subtask ID | $n \le$ | $q \le$ | Data Type | Score |
|---|---|---|---|---|
| $1$ | $100$ | $2000$ | A1 | $4$ |
| $2$ | $200$ | $2000$ | A3 | $13$ |
| $3$ | $2000$ | $2000$ | C2 | $10$ |
| $4$ | $5 \times 10^4$ | $2 \times 10^4$ | C1 | $11$ |
| $5$ | $5 \times 10^4$ | $2 \times 10^4$ | C2 | $13$ |
| $6$ | $10^5$ | $10^5$ | A3 | $15$ |
| $7$ | $10^5$ | $10^5$ | B1 | $4$ |
| $8$ | $10^5$ | $10^5$ | B2 | $7$ |
| $9$ | $2 \times 10^5$ | $2 \times 10^5$ | B3 | $12$ |
| $10$ | $2 \times 10^5$ | $2 \times 10^5$ | C3 | $11$ |
The data type contains two parameters. The first is one of A, B, or C:
- A: Only the third type of operation exists.
- B: The second type of operation does not exist.
- C: No special restrictions.
The second is one of 1, 2, or 3:
- 1: $k = 1$ is guaranteed.
- 2: $k$ is the same for all type 3 operations.
- 3: No special restrictions.
For $100\%$ of the data, $1 \le n, q \le 2 \times 10^5$, $0 \le m < n$, and $1 \le k \le 10^9$.