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