You are given a directed graph with $N$ vertices and $M$ edges. For $i = 1, 2, \ldots, M$, the $i$-th edge is directed from vertex $s_i$ to vertex $t_i$.

Determine whether there is a permutation $P = (P_1, P_2, \ldots, P_N)$ of $(1, 2, \ldots, N)$ that satisfies both of the following conditions, and if there is, provide an example.

-   $P_{s_i} \lt P_{t_i}$ for all $i = 1, 2, \ldots, M$.
-   $L_i \leq P_i \leq R_i$ for all $i = 1, 2, \ldots, N$.

The input is given from Standard Input in the following format:

```
$N$ $M$
$s_1$ $t_1$
$s_2$ $t_2$
$\vdots$
$s_M$ $t_M$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$
```

If there is no $P$ that satisfies the conditions, print `No`. If there is a $P$ that satisfies the conditions, print `Yes` in the first line, and the elements of $P$ separated by spaces in the second line, in the following format. If multiple $P$'s satisfy the conditions, any of them will be accepted.

```
Yes
$P_1$ $P_2$ $\ldots$ $P_N$
```

-   $2 \leq N \leq 2 \times 10^5$
-   $0 \leq M \leq \min\lbrace 4 \times 10^5, N(N-1) \rbrace$
-   $1 \leq s_i, t_i \leq N$
-   $s_i \neq t_i$
-   $i \neq j \implies (s_i, t_i) \neq (s_j, t_j)$
-   $1 \leq L_i \leq R_i \leq N$
-   All input values are integers.

Yes
3 1 4 2 5

P=(3,1,4,2,5) satisfies the conditions. In fact,

• for the first edge (s1,t1)=(1,5), we have P1=3<5=P5;
• for the second edge (s2,t2)=(2,1), we have P2=1<3=P1;
• for the third edge (s3,t3)=(2,5), we have P2=1<5=P5;
• for the fourth edge (s4,t4)=(4,3), we have P4=2<4=P3.

Also,

• L1=1≤P1=3≤R1=5,
• L2=1≤P2=1≤R2=3,
• L3=3≤P3=4≤R3=4,
• L4=1≤P4=2≤R4=3,
• L5=4≤P5=5≤R5=5.

No

No P satisfies the conditions, so print No.