Problem: Connect
Want to try solving this problem? You can submit your code online if you log in or register.
Connect
Input File: standard input
Output File: standard output
Time Limit: 1 second
Memory Limit: 128 MB
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.
Input
- 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 Li
between 1 and N, the label of the ith node. Each value of Li will appear twice.
Output
- 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.
Sample Input 1
3
1
1
3
2
3
2
Sample Input 2
3
1
1
3
2
2
3
Sample Output 1
1
1
2
1
2
1
Sample Output 2
1
1
1
1
1
1
Explanation
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.
Subtasks & Constraints
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.