Time Limit: | 1000ms |
Memory Limit: | 64000KiB |
Accepted: | 0 |
Submitted: | 0 |
X-Planet
CEOI 2000 Day 1 Problem 1
X-Planet
All the inhabitants of the
planet X build their houses in a triangular shape. In order to save time
and effort, they use a special construction method. Everything starts with
a straight wall. After that, for the construction of every new house they
just add two new walls to an already existing wall, thus resul-ting in a
closed, triangular shaped house. Of course, the two new added walls might
also be used as starting walls for new houses. Sometimes, using this
con-struc-tion pattern, they arrive at situations where some houses are
completely enclosed in others (like in the figure). However, this is not a
problem, because kids might live in the included houses.
To light up
their houses, the X-habitants install a light bulb on every corner of the
final construction (a bulb in a corner is common to all the houses sharing
that corner). On each corner, there is a switch whose touch toggles the
state (on/off) of the bulb from both that corner and also that of all the
bulbs of the connected corners. Two corners are considered connected if
they are placed at the end of the same wall.
Task
Write a program that finds a switch touch sequence that will turn on all the
light bulbs, starting from a given state.
Input
File name: X.IN
Line 1: N
an integer, the number of corners of the building, labelled from 1 to N;
Lines 2..2xN - 2: I J
Two integers, separated by a blank, representing a wall between the corners I and J;
Line 2xN - 1: S1S2 ... SN
N integers (separated by blanks) whose values are 0's or 1's, corresponding to the state of the N light bulbs;
0 means off; 1 means on.
The input data are guaranteed to represent a building that can be constructed in the specified pattern.
Output
File name: X.OUT
Line 1: L1 L2 ... LK
K integers, separated by blanks, represen-ting the list of the labels of the switches to be touched.
If there are several solutions, only one is required.
If there is no possible solution, you should write in the output file a single line containing the number 0.
Limits
3 <= N <= 1000
Sample Input
6
1 3
1 4
1 5
2 3
2 4
3 4
3 6
4 5
4 6
0 1 1 1 0 0
Sample Output
1 6
Note
In the figure below you can see a possible building steps for the example
file; the labels for the bulbs initially illuminated are underlined.
SubmitStatistics |