routes

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_i. A valid route is defined as a sequence of blocks, starting with X_i and ending with Y_i, such that Rar will travel from one block to the next in order.

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

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

Subtask 3 (20%): 1 ≤ N ≤ 500000. 1 ≤ Q ≤ 10⁶. E = N - 1. The graph is a tree.

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

Subtask 5 (26%): 1 ≤ N, E ≤ 500000. 1 ≤ Q ≤ 10⁶.

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