Want to try solving this problem? You can submit your code online if you log in or register.

You are building a critical electronic circuit for the xPhone 6, a new phone that will revolutionise the entire industry with its 2.2mm thinner body and 5.4% less curve on its corners than the obsolete and useless xPhone 5.

The electronic circuit you are building has the following form:

- There are 2N nodes on a main wire (a "bus"), electrically connected to
each other in a line.
- Each node also needs to be connected to exactly one other node with a new
wire you will place. The 2N nodes are labelled by integers between 1 and
N. There will be exactly two nodes with each label, and these N pairs of
nodes need to be connected to each other with N new wires.
- The circuit must be printed on to a flat circuit board, and no
wires can overlap. Each placed wire between two nodes will either be entirely
above the main wire, or entirely below.

The left image illustrates a valid wiring configuration. The middle image illustrates an invalid wiring configuration. The right image illustrates a valid wiring configuration that only places new wires above the main wire. Note that for the test case in the left and middle images, there is no valid wiring configuration that only places new wires above the main wire.

You must write a program that determines if it is possible to build the circuit with these constraints. If so, you must output for each node whether its new wire connects to it from above or below the main wire.

- The first line of input will contain one integer N, the number of pairs of nodes.
- The following 2N lines will each contain one integer L
_{i}between 1 and N, the label of the ith node. Each value of L_{i}will appear twice.

- If your program determines that there is no way to connect all pairs of
nodes, it should output one line containing
`0`. - Otherwise, your program should output 2N lines describing the way it
connects the pairs. The ith line should contain either
`1`or`2`. A`1`means the node is connected from above, and`2`means it is connected from below to the other node of the same label.

3 1 1 3 2 3 2

3 1 1 3 2 2 3

1 1 2 1 2 1

1 1 1 1 1 1

The first sample case corresponds to the case in the left and middle diagrams above. The second sample case corresponds to the case in the right diagram.

For all subtasks, 1 ≤ N ≤ 100,000.

- For Subtask 1 (20 points), 1 ≤ N ≤ 100 and the circuit is either
impossible to connect or only requires new wires above the main wire (that is,
either
`0`will be the correct output or 2N lines each containing`1`will be a correct outpt). - For Subtask 2 (20 points), 1 ≤ N ≤ 100.
- For Subtask 3 (20 points), 1 ≤ N ≤ 1,000.
- For Subtask 4 (20 points), the circuit is either
impossible to connect or only requires new wires above the main wire (that is,
either
`0`will be the correct output or 2N lines each containing`1`will be a correct outpt). - For Subtask 5 (20 points), no further constraints apply.

Privacy
statement

© Australian Mathematics Trust 2001-2024

Page generated: 27 February 2024, 12:30am AEDT