Broken Tree

Interview

Time limit1sMemory limit512 MB

Summary

Given a tree whose edges are oriented, flip as few edges as possible so that some vertex can reach every other vertex.

Level: Medium6 of 10
Topics: Tree, DFS, Greedy, Graph
Solved: No attempts yet

Problem

A greedy panda gnawed on a tree, and now the tree is broken!

The input gives a directed graph. Turning every edge of this graph into a bidirectional edge yields a tree.

You may flip the direction of any edge. Your goal is to flip as few edges as possible so that there exists a vertex satisfying the following.

Every vertex is reachable from this vertex.

Input

The first line gives the number of vertices $N$ . $(2 \le N \le 100,000)$

The next $N-1$ lines each give two integers $u, v$ . This means an edge directed from vertex $u$ to vertex $v$ . $(1 \le u, v \le N$ , $u ≠ v)$

Vertices are numbered from $1$ to $N$ . It is guaranteed that turning every edge of the graph into a bidirectional edge yields a tree.

Output

On the first line, output the edges that must be flipped as an $N-1$ -digit binary number. The $i$ -th bit from the left is 1 if the $i$ -th edge must be flipped, and 0 otherwise. The number of 1s appearing in the binary number must be minimized.

If there are multiple valid answers, output any one of them.

Examples2

Example 1
Input
```
5
2 4
2 3
3 1
5 1
```
Expected output
```
0001
```
Example 2
Input
```
6
5 1
3 1
3 4
2 4
2 6
```
Expected output
```
10100
```