Game

Time limit1sMemory limit512 MB

Summary

Given the pair query order, the program prints the smallest 0/1 answer string that keeps connectivity undecided until the last query.

Level: Hard8 of 10
Topics: Graph, Greedy, Game theory
Solved: No attempts yet

Problem

Jian-Jia is a boy who loves games. When someone asks him a question, he would rather turn it into a game than answer right away. Jian-Jia told his friend Mei-Yu about the flight network of Taiwan. There are $n$ cities, numbered $0$ through $n-1$ . Some pairs of cities are joined by a direct flight, and a flight can be taken in both directions.

Mei-Yu wanted to know whether she can travel between any two cities by plane, either directly or with stopovers. Instead of telling her, Jian-Jia proposed a game. Mei-Yu asks questions of the form "are city $x$ and city $y$ joined by a direct flight?", and Jian-Jia answers yes or no immediately. Mei-Yu asks about every pair of cities exactly once, so there are $r = n(n-1)/2$ questions in total.

Mei-Yu wins if there is some $i < r$ such that the first $i$ answers already settle whether travel between every pair of cities is possible. If she instead needs all $r$ answers, Jian-Jia wins.

To make the game more fun, the two agreed that Jian-Jia may forget the real flight network. He invents it as the questions arrive, and the only thing he must respect is his own earlier answers. A flight network agrees with the first $i$ answers when every pair answered yes is joined by a direct flight and every pair answered no is not. A pair that has not been asked yet may be joined or not. As long as two networks agree with the first $i$ answers, one of them connecting all cities and the other one not, Mei-Yu has settled nothing.

You are given the order in which Mei-Yu asks. Find the lexicographically smallest sequence of answers with which Jian-Jia wins, writing no as $0$ and yes as $1$ , where $0$ comes before $1$ . For $n \ge 2$ a winning sequence always exists.

Input

The first line contains the number of cities $n$ .

Each of the next $r = n(n-1)/2$ lines contains one question, in the order Mei-Yu asks. A line holds two different integers $x$ and $y$ separated by a space, which is the question of whether city $x$ and city $y$ are joined by a direct flight. Ignoring the order inside a pair, every pair $(x, y)$ appears exactly once in the input.

Output

Print one line with a string of length $r$ . Its $i$ -th character is Jian-Jia's answer to the $i$ -th question, written as $0$ for no and $1$ for yes. If several strings let Jian-Jia win, print the lexicographically smallest one.

Constraints

$2 \le n \le 100$
$0 \le x < n$ , $0 \le y < n$ , $x \ne y$

Examples4

Example 1
Input
```
2
0 1
```
Expected output
```
0
```
Example 2
Input
```
3
0 1
0 2
1 2
```
Expected output
```
010
```
Example 3
Input
```
4
0 1
0 2
0 3
1 2
1 3
2 3
```
Expected output
```
001010
```
Example 4
Input
```
4
1 2
0 3
0 1
2 3
1 3
0 2
```
Expected output
```
000110
```