History
Time limit1sMemory limit128 MB
Given directed precedence edges among up to 400 events, determine for each query pair whether one event's order relative to the other is fixed by transitivity.
Problem
Sejun knows Korean history very well and understands the chronological order of many historical events.
You are given some event-order relations that Sejun already knows. Write a program that answers whether the order of each requested pair of events can be determined from those relations.
Input
The first line contains two natural numbers, n and k, where n is the number of events (n <= 400) and k is the number of known order relations (k <= 50,000).
Each of the next k lines contains two event numbers. The first event happened before the second event. The given relations are never contradictory.
The next line contains a natural number s, the number of event pairs to query (s <= 50,000). Each of the next s lines contains two different event numbers.
All event numbers are natural numbers from 1 through n.
Output
Print one answer for each of the s queries.
For each query, print -1 if the first event is known to have happened before the second event. Print 1 if the second event is known to have happened before the first event. Print 0 if their order cannot be determined.