Race Map Labeling

Time limit2sMemory limit256 MB

Summary

Simulate the smallest-first label-flipping process on the graph and print every place with its final label.

Level: Medium5 of 10
Topics: Simulation, Graph
Solved: No attempts yet

Problem

The organizing committee of a motorcycle race labels the contest map. The map has $n$ places numbered $0$ through $n-1$ . Every road is bidirectional and joins two different places.

Each place gets the label $0$ for regular or $1$ for service. If $d_i$ roads reach place $i$ , then at most $\lfloor d_i / 2 \rfloor$ of its neighbors may carry the same label as place $i$ . Several labelings usually satisfy that rule, so only the labeling produced by the following procedure counts as correct.

Give every place the label $0$ .
While some place breaks the rule, take the smallest-numbered such place and flip its label: $0$ becomes $1$ , and $1$ becomes $0$ .
Repeat step 2 until no place breaks the rule.

Each flip raises the number of roads whose two ends carry different labels by at least $1$ , so the procedure always stops after finitely many flips.

Input

The first line contains the number of places $n$ . ( $1 \le n \le 1000$ )

Each of the next $n$ lines describes one place, line $i$ describing place $i$ . ( $i = 0, 1, \dots, n-1$ ) A line has this form.

number_of_neighbors: neighbor1 neighbor2 ... neighborm

number_of_neighbors is the number of roads reaching place $i$ , followed by the numbers of the neighboring places separated by spaces. The line 2: 1 2 means two neighbors, numbered $1$ and $2$ .

No road joins a place to itself, and two places are joined by at most one road. If $b$ appears in the neighbor list of place $a$ , then $a$ appears in the neighbor list of place $b$ . The line of a place with no neighbor ends right after the colon.

Output

Print $n$ on the first line. Then print $n$ lines, one per place starting from place $0$ , each carrying the label the procedure produced. A line has this form.

label number_of_neighbors: neighbor1 neighbor2 ... neighborm

label is $0$ for a regular place and $1$ for a service place. Print the neighbor list in the order it was given in the input. Separate tokens with one space, and put the colon directly after number_of_neighbors. The line of a place with no neighbor ends right after the colon.

Examples6

Example 1

Input

Expected output

Example 2
Input
```
1
0:
```
Expected output
```
1
0 0:
```
Example 3
Input
```
2
1: 1
1: 0
```
Expected output
```
2
1 1: 1
0 1: 0
```

Example 4

Input

6
5: 1 2 3 4 5
1: 0
1: 0
1: 0
1: 0
1: 0

Expected output

6
1 5: 1 2 3 4 5
0 1: 0
0 1: 0
0 1: 0
0 1: 0
0 1: 0

Example 5

Input

Expected output

Example 6

Input

Expected output