Experiment

Witek and his friends are building a maze for ants. The maze has $N$ chambers numbered from $0$ to $N-1$, connected by one-way corridors. Once an ant is placed in a chamber, it keeps walking, at each step picking at random one of the outgoing corridors of its current chamber, and it stops only when it reaches a chamber with no outgoing corridor.

Some corridors already have a fixed direction; the rest are dug, but their direction has not been chosen yet. Your task is to choose a direction for every undecided corridor so that no ant can ever walk forever. In other words, once all directions are chosen, the whole maze (all corridors together) must contain no directed cycle.

The first line contains three integers $N$, $A$, and $B$ ($1 \le N, A, B \le 200000$): the number of chambers, the number of corridors whose direction is already fixed, and the number of corridors whose direction is still undecided.

Each of the next $A$ lines contains two integers $S$ and $K$, describing a fixed corridor that goes from chamber $S$ to chamber $K$.

Each of the following $B$ lines contains two integers $S$ and $K$, describing an undecided corridor that connects chambers $S$ and $K$.

For every corridor, $S \ne K$. It is guaranteed that a valid orientation exists, which is equivalent to saying that the corridors with a fixed direction contain no directed cycle.

Many orientations may keep every ant from walking forever, so to make the answer unique we ask for one specific valid orientation, defined as follows.

Look only at the corridors that already have a fixed direction. Because a valid orientation exists, these fixed corridors form a directed acyclic graph. Build a canonical ordering of the chambers with this process: counting each chamber's in-degree over the fixed corridors only, repeatedly take the smallest-numbered chamber whose current in-degree is $0$, append it to the ordering, and remove its outgoing fixed corridors (decreasing the in-degree of each target chamber by $1$). After this process every chamber has a distinct position.

Then, following the input order, print one line for each undecided corridor:

• print 0 if $S$ comes before $K$ in the ordering (the corridor is directed from $S$ to $K$),
• print 1 otherwise (the corridor is directed from $K$ to $S$).

Orienting every corridor from the earlier chamber to the later chamber in this ordering guarantees that no ant can walk forever.