AIOC Banner

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:

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

Output

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.

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated:  6 December 2019,  9:03pm AEDT