Itinerary in a Tree

The Scientific Committee is planning to visit n cities. The cities are connected by exactly n-1 roads and form a tree (i.e. a connected acyclic graph). Each road i connects cities u[i] and v[i].

Every city has an airport. The committee will start their trip by flying from Singapore into some starting city. They wish to conduct a tour of the cities. A tour is defined as a closed walk that uses each road exactly twice (once in each direction) so that each city is visited at least once. In any tour the number of city visits is always 2n-1 and the tour always ends at the starting city.

The committee also wants to attend m events, which are scheduled in a fixed order from 1 to m. The j-th event is held in city s[j]. Note that events happen in different cities consecutively (i.e. s[j] ≠ s[j+1] for all valid j).

A tour is called an itinerary if the event sequence appears as a subsequence in the tour; that is, if by deleting some (or no) cities from the tour’s vertex sequence (of length 2n-1) one obtains s[1], s[2], …, s[m] in order (though not necessarily consecutively).

The committee has not decided on a starting city yet. They call a city x a good starting city if there exists at least one itinerary (i.e. a tour starting at x that contains the event sequence as a subsequence). For each city you are to decide whether it is good to start the tour from that city.

Observations and Hints:

• In any tour of the tree, every road is traversed twice. Thus if a city (other than the starting city) has degree d, it is visited exactly d times. The starting city is visited one extra time, hence deg(start) + 1 times.
• Since the event sequence must be a subsequence of the tour, the number of occurrences of a city v in the event sequence cannot exceed the number of times v appears in the tour. That is, for any city v (if v is not the starting city) we must have: $$\text{freq}(v) \leq \text{deg}(v),$$ and if v is chosen as the starting city then: $$\text{freq}(v) \leq \text{deg}(v)+1.$$
• Using the freedom in choosing the order in which to traverse adjacent roads in a tree, one can show that the necessary count conditions stated above are also sufficient for the existence of an itinerary.

Your task is to, for each city, output 1 if it can be chosen as the starting city (i.e. there exists an itinerary starting there) or 0 otherwise.

inputFormat

The first line contains two integers n and m (n ≥ 2), the number of cities and the number of events.

The next n-1 lines each contain two integers u and v (1 ≤ u, v ≤ n), denoting a road between cities u and v.

The last line contains m integers s[1], s[2], …, s[m] (1 ≤ s[j] ≤ n for each j), describing the cities at which events are held. It is guaranteed that s[j] ≠ s[j+1] for all valid j.

outputFormat

Output a binary string of length n. The i-th character should be '1' if there exists an itinerary starting from city i, and '0' otherwise.

sample

2 2
1 2
1 2

11