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 L_i between 1 and N, the label of the ith node. Each value of L_i 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

Sample Input 2

Sample Output 1

Sample Output 2

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.