COCI '15 Contest 3 #3 Molekule

Points: 10

Time limit: 0.6s

Memory limit: 64M

Problem type

Scientists in a chemical lab in Croatia have been studying the chemical bonds between different molecules. They have a special interest in a group of molecules of the chemical compound nitro hydrogen laminate.

The compound consists of $N$ ~N~ molecules bound together by $N - 1$ ~N - 1~ covalent bonds and all the molecules are directly or indirectly tied together with bonds in a single structure.

The scientists want to modify the compound in a way that all the covalent bonds are transformed into directed covalent bonds. Because of the instability of the newly created compound, each molecule will have a large number of impulses coming out of it and travelling to other molecules using the directed bonds. An impulse can travel using the directed covalent bond only in the direction of the bond itself.

$\text{[math]}$

The instability of the compound is defined as the largest possible number of bonds a single impulse can use to travel. The scientists want to direct the compound's covalent bonds in a way that the newly created compound is as stable as possible. In other words, their goal is to create a compound with the minimal longest path an impulse can take during its travel.

Help the scientists determine the direction of each covalent bond in the compound.

Input Specification

The first line of input contains the integer $N$ ~N~ $(2 \le N \le 100\,000)$ ~(2 \le N \le 100\,000)~.

Each of the $N - 1$ ~N - 1~ lines contains the integers $a_i$ ~a_i~ and $b_i$ ~b_i~ $(1 \le a_i, b_i \le N)$ ~(1 \le a_i, b_i \le N)~ that denote that molecules $a_i$ ~a_i~ and $b_i$ ~b_i~ are connected with a covalent bond.

In test cases worth at least 30% of total points, it will hold $N \le 20$ ~N \le 20~.

Output Specification

Output $N - 1$ ~N - 1~ lines, where each line must contain 1 if the covalent bond is going to be directed from $a_i$ ~a_i~ to $b_i$ ~b_i~, otherwise it contains 0.

If there are multiple possible solutions, output any.

Sample Input 1

3
1 2
2 3

Sample Output 1

1
0

Explanation for Sample Output 1

The example corresponds to the left image from the task. The longest path an impulse can take is $1$ ~1~. Notice that 0 1 is also a correct solution.

Sample Input 2

Sample Output 2

0
1
0

Explanation for Sample Output 2

The example corresponds to the right image from the task.

Comments

0

sre0x2a commented on May 5, 2025, 7:34 p.m.

For the first test case how does 0 0 0 0 not pass? According the instructions it is the minimal longest path to be the most stable. I think the accepted answer they want is 0 1 0 0 which has a longest path of 2 from the root 5. But that is the same longest path of 2 from the root 2. How is 0 0 0 0 then not an acceptable answer as well? Is it suppose to be the minimal number of vertices at the minimal longest path depth? This is the type of stuff that kind of makes these problems frustrating. I understand it is our job to understand what the question is asking but the author could do a much better job of removing the vagueness of these problems. Like I don't know having an example to display what it is you EXACTLY mean as the minimal longest path.

1

spheniscine commented on May 8, 2025, 2:02 a.m. ← edited →

You must have misunderstood something, as the minimal longest path is not 2

0

sre0x2a commented on May 9, 2025, 7:45 p.m.

Oh I was way off in understanding for sure