Hashgraph

When users on a network communicate without going through a central server, one problem is the ordering of the communications, that is, who communicated first. Defining the order clearly is very important in systems where a mix-up in order is fatal, such as money transfers. One data structure proposed to solve this problem is the hashgraph. Before explaining it, note that this problem borrows some concepts from Baird's academic paper 'Hashgraph consensus'. (Baird, Leemon. "The swirlds hashgraph consensus algorithm: Fair, fast, byzantine fault tolerance." Swirlds Tech Reports SWIRLDS-TR-2016-01, Tech. Rep. (2016).)

A hashgraph records, among N users, who communicated what to whom in what order, in the form of a graph that grows unidirectionally with width N. The vertices of the graph are called events and hold transaction information. An edge connects the sender's last event to the event the receiver created.

For easy understanding, look at the picture of a hashgraph in which four users A, B, C, D communicate.

In the picture above, the four users A, B, C, D all start with their first events A1, B1, C1, D1.

First, B communicates to D and creates event 1. Event 1 holds information about B's and D's last events, B1 and D1. At this moment A and C do not know that event 1 exists. D communicates to B and creates event 2, and when B communicates to A and A creates event 3a, only then can A trace back from event 3a through event 2 and learn that event 1 exists. Because each event holds information about the sender's and receiver's last events, one user A communicating to B means A passes all the communication records A knows to B.

Meanwhile, events 1, 2, 3a have a precedence relation, so their order is clear. But the order of events such as 3a, 3b, 3c is hard to decide easily. The precedence relation of these events is defined by taking the event that spreads to more users more quickly as having happened first. A hashgraph uses complex concepts and theorems to define this precedence relation in a mathematically rigorous way, but in this problem we only look at the basic concepts simply.

• If a precedence relation exists between two events, as with 3a and 2 or 3a and B1, then 3a can see 2 (B1) (x can see y). The converse holds only when x = y.

A hashgraph proves mathematically that the order of all events can be defined using this "see" concept between events and a few additional concepts.

Given a hashgraph and two events, write a program that checks whether one node can see another node.

The first line gives the number of users N (2 ≤ N ≤ 100) and the number of all communication events M (1 ≤ M ≤ 10,000) in the hashgraph. (Each user's first event, which has no sender, is excluded.)

From the second line, M lines follow, each giving the information that user i communicated to user j. (0 ≤ i, j ≤ N-1)

The (M+2)-th line gives user A's p-th event and user B's q-th event. (0 ≤ A, B ≤ N-1) p and q are given only as input values for events that A and B actually have.

Let the 0-th event mean the first event each user creates, which receives a communication from no user (A1, B1, C1, D1 in the picture example).

Output 1 if user A's p-th event can see user B's q-th event, and 0 if not.