#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

Rar lives in a town with *N* blocks and *E* roads connecting two blocks *A _{i}* and

*B*.

_{i}To be healthy, Rar has created an exercise regime for himself, lasting *D* days. Each day, Rar will travel a route from block *X _{i}* to block

*Y*. A valid route is defined as a sequence of blocks, starting with

_{i}*X*and ending with

_{i}*Y*, such that Rar will travel from one block to the next in order.

_{i}Rar is weird. On some days, he feels like picking a route with an *odd* number of roads, and on other days he feels like picking one with an *even* number of roads.

For each day, help Rar determine whether there exists an odd and/or even length path from his designated start and end blocks.

## Input

The first line of input will contain three integers, *N*, *E* and *D*.

The next *E* lines of input will contain two integers each, *A _{i}* and

*B*.

_{i}The next *D* lines of input will contain two integers each, *X _{i}* and

*Y*.

_{i}## Output

For each day, the output should contain a string ("odd", "even", "none" or "both"), describing the parity of the available paths.

## Limits

0 ≤ A_{i}, B_{i}, X_{i}, Y_{i} < N.

Subtask 1 (15%): 1 ≤ N, E ≤ 1000. 1 ≤ Q ≤ 10^{6}.

Subtask 2 (16%): 1 ≤ N, E ≤ 500000. Q = 1.

Subtask 3 (20%): 1 ≤ N ≤ 500000. 1 ≤ Q ≤ 10^{6}. E = N - 1. The graph is a **tree**.

Subtask 4 (23%): 1 ≤ N ≤ 500000. 1 ≤ Q ≤ 10^{6}. E = N. The graph is connected.

Subtask 5 (26%): 1 ≤ N, E ≤ 500000. 1 ≤ Q ≤ 10^{6}.

Subtask 6 (0%): Sample Testcases.

## Sample Testcase 1

### Input

6 5 3 0 1 1 5 1 2 2 4 2 3 3 5 2 1 1 4

### Output

odd odd even

## Sample Testcase 2

### Input

9 8 5 0 1 1 2 4 7 4 5 5 6 5 8 6 7 0 2 3 7 1 2 5 7 4 5 3 0

### Output

none both even odd none

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 15 | 22 | 1s | 256MB | Minimum |

2 | 16 | 20 | 1s | 256MB | Minimum |

3 | 20 | 20 | 1s | 256MB | Minimum |

4 | 23 | 20 | 1s | 256MB | Minimum |

5 | 26 | 102 | 1s | 256MB | Minimum |

6 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o routes -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512