A secret intelligence agency (which is even too secret to mention its name here) controls agents around the world. From time to time the headquarters need to send out a message to all agents. For obvious reasons, the transmission must be as secure as possible.
The agency’s executives mistrust electronic communication and therefore transfer their messages by contact persons (in short: contacts). They organized agents and contacts into a large network; each contact is responsible for transporting information from exactly one agent to another, and only in this one direction. Nonetheless there might be more than one contact to transport information between two agents.
When the headquarters send out a message, their “message officer” uses some of his own contacts to transport it to a number of field agents. Those agents use their contacts to forward the message to other agents, and so on until it eventually reaches every single agent. However, in order to reduce risk, the number of times a message is transported by contacts should be minimized (i.e. no agent should receive the same message twice). Therefore an agent doesn’t forward a message using all of his contacts but obeys a “transmission scheme” for this message. A transmission scheme contains information on how a message is to be forwarded by the agents.
Recently, the agency found out that some contacts misused confidential information. For this reason, they decided to split each message into two parts which are both useless if not read together. They now send out the two parts but without using the same contact twice. Therefore no contact will see the full message. Nonetheless it is important that every agent eventually receives both parts of the message. The agency now wonders how to create valid transmission schemes for each part that satisfy the above conditions.
입력 4 6 1 2 1 3 2 3 3 2 2 4 2 4 출력 1 3 5 2 4 6
출처:ceoi/2008/