Cow Departure Order

There are \(N\) cows that have gathered from around the world to attend a huge party. The cows form a tree‐structure friendship network (i.e. there are \(N-1\) pairs of cows that are friends and any cow can reach any other cow via some sequence of friends). When the party is over, the cows will leave one by one. They wish to choose a departure order so that as long as at least two cows remain, every remaining cow still has at least one friend who has not yet left.

In addition, due to luggage storage restrictions, there are \(M\) precedence constraints. Each constraint is given as a pair \((a_i, b_i)\), meaning that cow \(a_i\) must leave before cow \(b_i\). Note that these two cows may or may not be friends.

Your task is to help the cows determine, for every cow, whether it is possible for her to be the last cow to leave under some valid departure order. It is possible that no valid departure order satisfying all the conditions exists.

Note on the departure order: When at least two cows remain, the cow leaving at that moment must be a leaf in the induced subgraph (i.e. it has at most one friend among those cows that have not yet left).

inputFormat

The first line contains two integers \(N\) and \(M\) \( (1 \leq N \leq 10,\; 0 \leq M \leq 20) \) representing the number of cows and the number of precedence constraints, respectively.

The following \(N-1\) lines each contain two integers \(u\) and \(v\) \((1 \le u,v \le N)\) indicating that cow \(u\) and cow \(v\) are friends. It is guaranteed that these edges form a tree.

The next \(M\) lines each contain two integers \(a_i\) and \(b_i\) \((1 \le a_i,b_i \le N)\) meaning that cow \(a_i\) must leave before cow \(b_i\). If \(M = 0\) then no such lines appear.

outputFormat

If there is no valid departure order satisfying all the conditions, output a single line containing -1.

Otherwise, output \(N\) lines. The \(i\)th line should be 1 if cow \(i\) can be the last to leave in some valid departure order, and 0 otherwise.

sample

3 0
1 2
2 3

0
1
0