[Solution] Madoka and The First Session Codeforces Solution

F. Madoka and The First Session

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Oh no, on the first exam Madoka got this hard problem:

Given integer 𝑛$n$ and 𝑚$m$ pairs of integers (𝑣𝑖,𝑢𝑖$v_i,u_i$). Also there is an array 𝑏1,𝑏2,…,𝑏𝑛$b_1,b_2,\dots ,b_n$, initially filled with zeros.

Then for each index 𝑖$i$, where 1≤𝑖≤𝑚$1\le i\le m$, perform either 𝑏𝑣𝑖:=𝑏𝑣𝑖−1$b_{v_i}:=b_{v_i}-1$ and 𝑏𝑢𝑖:=𝑏𝑢𝑖+1$b_{u_i}:=b_{u_i}+1$, or 𝑏𝑣𝑖:=𝑏𝑣𝑖+1$b_{v_i}:=b_{v_i}+1$ and 𝑏𝑢𝑖:=𝑏𝑢𝑖−1$b_{u_i}:=b_{u_i}-1$. Note that exactly one of these operations should be performed for every 𝑖$i$.

Also there is an array 𝑠$s$ of length 𝑛$n$ consisting of 0$0$ and 1$1$. And there is an array 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$, where it is guaranteed, that if 𝑠𝑖=0$s_i=0$ holds, then 𝑎𝑖=0$a_i=0$.

Help Madoka and determine whenever it is possible to perform operations in such way that for every 𝑖$i$, where 𝑠𝑖=1$s_i=1$ it holds that 𝑎𝑖=𝑏𝑖$a_i=b_i$. If it possible you should also provide Madoka with a way to perform operations.

Input

The first line contains two integers 𝑛$n$ and 𝑚$m$ (2≤𝑛≤10000,1≤𝑚≤10000$2\le n\le 10000,1\le m\le 10000$) — the length of the array 𝑎$a$ and the number of pair of integers.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

The second line contains 𝑛$n$ integers 𝑠1,𝑠2,…𝑠𝑛$s_1,s_2,\dots s_n$ (0≤𝑠𝑖≤1$0\le s_i\le 1$) — the elements of the array 𝑠$s$.

The third line contains 𝑛$n$ integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (|𝑎𝑖|≤𝑚$|a_i|\le m$) — the elements of the array 𝑎$a$. It is guaranteed that if 𝑠𝑖=0$s_i=0$ holds, then 𝑎𝑖=0$a_i=0$.

𝑖$i$-th of the following 𝑚$m$ lines contains two integers 𝑣𝑖$v_i$ and 𝑢𝑖$u_i$ (1≤𝑣𝑖,𝑢𝑖≤𝑛,𝑣𝑖≠𝑢𝑖$1\le v_i,u_i\le n,v_i\ne u_i$) — the indexes of the elements of the array 𝑏$b$ to which the operation is performed. It is also guaranteed that there are no two indices 𝑖$i$ and 𝑗$j$, where 1≤𝑖<𝑗≤𝑚$1\le i<j\le m$, such that (𝑣𝑖,𝑢𝑖)=(𝑣𝑗,𝑢𝑗)$(v_i,u_i)=(v_j,u_j)$ or (𝑣𝑖,𝑢𝑖)=(𝑢𝑗,𝑣𝑗)$(v_i,u_i)=(u_j,v_j)$.

Output

In the first line print "YES" if it is possible to perform operations in the required way, and "NO" otherwise.

You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).

In case you printed "YES", print 𝑚$m$ pairs of integers. If for pair (𝑣𝑖,𝑢𝑖)$(v_i,u_i)$ we should perform 𝑏𝑣𝑖:=𝑏𝑣𝑖−1$b_{v_i}:=b_{v_i}-1$ and 𝑏𝑢𝑖:=𝑏𝑢𝑖+1$b_{u_i}:=b_{u_i}+1$, print (𝑣𝑖,𝑢𝑖)$(v_i,u_i)$. Otherwise print (𝑢𝑖,𝑣𝑖)$(u_i,v_i)$. If there are multiple ways to get the correct answer, you can print any of them.

You can print pairs in any order.