routes

Problem Description

Rar lives in a town with N blocks and E roads connecting two blocks Ai and Bi.

To be healthy, Rar has created an exercise regime for himself, lasting D days. Each day, Rar will travel a route from block Xi to block Yi. A valid route is defined as a sequence of blocks, starting with Xi and ending with Yi, 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, Ai and Bi.

The next D lines of input will contain two integers each, Xi and Yi.

Output

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

Limits

0 ≤ Ai, Bi, Xi, Yi < N.

Subtask 1 (15%): 1 ≤ N, E ≤ 1000. 1 ≤ Q ≤ 106.

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

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

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

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

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

Time Limit: 1 Seconds
Memory Limit: 256MB
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 15
2 16
3 20
4 23
5 26
6 0