Teleports
(Running time - 1s.)
Great sorcerer Byter created two islands on the Baltic See: Bornholm
and Gotland. On each island he has installed some magical teleports. Each
teleport can work in one of two modes:
-
receiving--one can be teleported to it,
-
sending--anyone who enters the teleport is transfered to the specific destination
teleport on the other island, provided that the other teleport is in the
receiving mode.
Once, Byter gave his apprentices the following task: they must set the
teleports' modes in such a way, that no teleport is useless, i.e. for each
teleport set in the receiving mode there must be at least one teleport
sending to it, set in the sending mode; and vice versa, for each teleport
set in the sending mode, the destination teleport must be set in the receiving
mode.
Task
Write a program that:
-
reads the description of the teleports on both islands, form the input
file tel.in,
-
determines the appropriate modes for teleports,
-
writes the result to the output file tel.out.
If there are several possible solutions, your program should output just
one of them.
Input
In the first line of the text file tel.in, there are two integers
m and n, 1<=m,n<=50 000, separated by a single
space; m is the number of teleports on Bornholm, and n is
the number of teleports on Gotland. Teleports on both islands are numbered
from 1 to m and n respectively. The second line of the file
contains m positive integers, not greater than n, separated
by single spaces--k-th of these integers is the number of the teleport
on Gotland that is the destination of the teleport k on Bornholm.
The third line contains analogous data for teleports on Gotland, i.e. n
positive integers, not greater than m,separated by single spaces--k-th
of these integers is the number of the teleport on Bornholm that is the
destination of the teleport k on Gotland.
Output
Your program should write two lines describing the modes of the teleports,
respectively, on Bornholm and Gotland, to the output file tel.out.
Both lines should contain a string of, respectively, m or n
ones and/or zeros. If the k-th character in the string is 1,
then the k-th teleport is in the sending mode, and if it is 0,
than the corresponding teleport is in the receiving mode.
Example
Input file tel.in:
4 5
3 5 2 5
4 4 4 1 3
Correct output file tel.out
0110
10110