시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 (추가 시간 없음) 512 MB111100.000%

문제

John's father recently passed away and left John a colored graph and a machine. The colored graph was simply a connected undirected graph with labels $0$ or $1$ on each of its vertices. The machine was something more peculiar.

A machine of order $n$ is an acyclic directed graph with one source (a vertex with no incoming edges) and two sinks (vertices with no outgoing edges). One of the sinks is labeled with $0$ and the other is labeled with $1$. Each of the remaining vertices including the source is labeled with an integer from $\{1, \ldots, n\}$ and has exactly two outer edges: one labeled with $0$ and the other labeled with $1$. Also on every path from the source to a sink, all labels of the non-sink vertices are distinct

A machine of order $n$ computes a function from $\{0,1\}^n$ to $\{0,1\}$. Let us define it recursively. For $0$-sink, the function is $0$ on every input, for $1$-sink, it is $1$ for every input. For a non-sink vertex $v$ labeled with $i$, $$f_v(x_1, \ldots, x_n) = \begin{cases} f_{t_0} (x_1, \ldots, x_n) & \text{if } x_i = 0 \\ f_{t_1} (x_1, \ldots, x_n) & \text{if } x_i = 1 \end{cases}$$ where $t_j$ is the end of the edge from $v$ labeled with $j$ for $j \in \{0,1\}$. The function calculated by a machine with the source $s$ is $f_s$.

In his will, Jonh's father wrote that he had worked on the machine for years in order to calculate the edge-coloring function of the colored graph he had given to John. All he asks John is to check if the machine calculates this function correctly. 

The edge-coloring function $\mathrm{EC}(x_1, \ldots, x_m)$ of a colored graph $G$ with $\ell$ vertices and $m$ edges with vertex-labels $c_1, \ldots, c_{\ell}$ is a function from $\{0,1\}^m$ to $\{0,1\}$. It equals $1$ if and only if for every vertex $v$ with incident edges $e_1, \ldots, e_k$, the following equality holds: $c_v = \bigoplus\limits_{i=1}^k x_{e_i}$. In other words, the parity of the sum of values on edges incident to $v$ is $c_v$.

You are asked to check if the given machine calculates the edge-coloring function of the given graph, and if it is not, find the coloring of edges $x$ such that $\mathrm{EC}(x) \neq f(x)$, where $f$ is the function calculated by the machine.

입력

The first line contains five integers $N$, $m$, $s$, $t_0$, and $t_1$: the number of nodes in the machine, the order of the machine, the index of the source and the indices of the $0$-sink and $1$-sink respectively ($1 \le s, t_0, t_1 \le N \le 300\,000$; $N \ge 3$; $1 \le m \le 300\,000$; $t_0 \neq t_1$; $s \neq t_0$; $s \neq t_1$). The $i$-th of the next $N$ lines describes the $i$-th node of the machine. It contains three integers $o_0$, $o_1$ and $\ell$: the index of the end node of the outer edge from the node $i$ labeled with $0$, this index for the edge labeled with $1$, and the label of the node $i$ itself ($-1 \le o_0, o_1 \le N$; $-1 \le \ell \le m$). If $i$ is a sink, $o_0 = o_1 = \ell = -1$. The values $o_0$, $o_1$ and $\ell$ are never equal to zero.

It is guaranteed that

  • the graph of the machine is acyclic;
  • $o_0$, $o_1$ or $\ell$ are equal to $-1$ if and only if the node is a sink;
  • on every path from the source to a sink, all labels of non-sink vertices are unique;
  • all vertices except maybe one of the sinks are reachable from $s$.

The next line contains one integer $k$, the number of vertices in the colored graph $G$ ($1 \le k \le 300\,000$). The number of edges in this graph is $m$. The following line contains $k$ integers $c_1, c_2, \ldots, c_k$, the labels of the vertices of $G$ (each $c_i$ is either $0$ or $1$).

The last $m$ lines contain descriptions of the edges of $G$. The $i$-th of these lines contains two integers $a_i$ and $b_i$ which describe an edge connecting $a_i$ and $b_i$ ($1 \le a_i, b_i \le k$; $a_i \neq b_i$). It is guaranteed that $G$ is connected, but it may contain parallel edges.

출력

Print "YES" on the first line if the machine calculates the edge-coloring function correctly. Otherwise, print "NO" on the first line, and on the next line, print $m$ characters $x_1, x_2, \ldots, x_m$ such that $\mathrm{EC}(x_1, x_2, \ldots, x_m) \neq f(x_1, x_2, \ldots, x_m)$, where $f$ is the function computed by the machine. Each $x_i$ must be either $0$ or $1$.

예제 입력 1

7 3 1 6 7
2 3 1
6 4 2
5 6 2
6 7 3
7 6 3
-1 -1 -1
-1 -1 -1
3
1 1 0
1 2
1 3
2 3

예제 출력 1

YES

예제 입력 2

7 3 1 6 7
2 3 1
6 4 2
5 6 2
6 7 3
6 7 3
-1 -1 -1
-1 -1 -1
3
1 1 0
1 2
1 3
2 3

예제 출력 2

NO
101

예제 입력 3

3 1 1 2 3
2 3 1
-1 -1 -1
-1 -1 -1
2
1 1
1 2

예제 출력 3

YES