BOI 2001 Day 2 Problem 3
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:
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.
TaskWrite a program that:
If there are several possible solutions, your program should output just one of them.
InputIn 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.
OutputYour 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.
4 5 3 5 2 5 4 4 4 1 3