New Year's '19 P2 - Ball Sculpture

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 256M

Problem type

Your younger sibling got a new toy for Christmas: a set of balls, tracks, and switches!

A ball sculpture is a construction made out of said tracks and switches where a small ball is placed at the top of the sculpture and travels down the tracks to the bottom. In between the top and bottom of the sculpture, there are N switches that control the path that the ball takes.

The switches are labelled from 1 to N in order of height from the top of the sculpture to the bottom. Each switch i has two output tracks which each lead either to another switch further down in the sculpture, or go directly to the bottom of the sculpture. This is denoted by two values a_i and b_i where i < a_i, b_i \le N+1, where a value of N+1 represents the track going to the very bottom.

A switch can be in one of two states: 0 or 1. If a ball arrives while it is in state 0, the ball goes down a track to a_i, but if it is in state 1, it goes to b_i. In either case, the state of the switch is flipped to the opposite state.

Initially, all switches are in state 0. Then, a sequence of M balls are placed at the top of the sculpture, where the previous ball must reach the bottom of the sculpture before the next ball is placed.

Bored, your younger sibling asks you: what is the final state of all the switches after all M balls reach the bottom?


1 \le N \le 10^6

1 \le M \le 10^9

i < a_i, b_i \le N+1

Input Specification

The first line contains two space-separated integers N and M.

N lines follow; the i-th one contains two space-separated integers a_i, b_i.

Output Specification

Output N digits on a single line, with the i-th digit being the state of switch i.

Sample Input 1

3 5
2 3
4 4
4 4

Output for Sample Input 1


Explanation for Output for Sample Input 1

The sequence of states is 000, 110, 011, 101, 000, 110.

Sample Input 2

4 11
5 2
5 3
5 4
5 5

Output for Sample Input 2



There are no comments at the moment.