oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

routes Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

routes.html

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

Tags

Graph Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
115221s256MBMinimum
216201s256MBMinimum
320201s256MBMinimum
423201s256MBMinimum
5261021s256MBMinimum
6021s256MBMinimum

Judge Compile Command

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

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.