One Ball Stays - Repovive Premier Round 8 | Repovive

24D. One Ball Stays

2000 pts2s256 MB

You are given a simple connected undirected graph with $n$ vertices and $m$ edges. Initially, vertex $v$ contains $a_v$ balls.

In one operation, choose two adjacent vertices and keep one ball at one of them. Swap all the remaining balls between the two vertices.

Formally, choose an ordered pair of adjacent vertices $(u,v)$ such that vertex $u$ currently contains at least one ball. If their current numbers of balls are $x$ and $y$ , respectively, replace them simultaneously by $y+1$ and $x-1$ . All other vertices remain unchanged.

Determine whether, after zero or more operations, every vertex $v$ can contain exactly $b_v$ balls.

Constraints

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$n-1 \le m \le 2 \times 10^5$
$0 \le a_v,b_v \le 10^9$
$1 \le u_i,v_i \le n$
The graph is simple, connected, and undirected.
The sum of $n$ over all test cases is at most $2 \times 10^5$ .
The sum of $m$ over all test cases is at most $2 \times 10^5$ .

Input

t

\left. \begin{array}{l} n \quad m \\ a_1 \quad a_2 \quad \ldots \quad a_n \\ b_1 \quad b_2 \quad \ldots \quad b_n \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array} \right\} \times t

Output

\left. \begin{array}{l} \texttt{Yes} \;\text{or}\; \texttt{No} \end{array} \right\} \times t

The answer is case-insensitive. Any capitalization of the letters is accepted, including $\texttt{YES}$ , $\texttt{yes}$ , and $\texttt{YeS}$ .

Samples

Input

Case 1

Case 2

Explanation

Case 1

Choose vertices 1 and 2, keeping one ball at vertex 1. The counts change from (4,1) to (2,3), which is the required configuration.

Case 2

The only legal choice keeps the ball at vertex 1 and leaves the configuration unchanged. The ball can never reach vertex 2.

Output

Case 1

Yes

Case 2

No

Input

Case 1

Case 2

Case 3

Explanation

Case 1

One possible sequence of configurations is (3,0,0), (1,2,0), (1,1,1), (2,1,0), (0,3,0). In these four operations, the ordered pairs of chosen vertices are (1,2), (2,3), (1,3), and (2,1), respectively; the first vertex of each pair keeps one ball.

Case 2

The counts are the same as in the preceding example, but vertices 1 and 3 are not adjacent. No sequence of legal operations reaches the required configuration.

Case 3

The initial configuration already equals the required configuration, so zero operations suffice.

Output

Case 1

Yes

Case 2

No

Case 3

Yes

You are given a simple connected undirected graph with $n$ vertices and $m$ edges. Initially, vertex $v$ contains $a_v$ balls.

In one operation, choose two adjacent vertices and keep one ball at one of them. Swap all the remaining balls between the two vertices.

Determine whether, after zero or more operations, every vertex $v$ can contain exactly $b_v$ balls.

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$n-1 \le m \le 2 \times 10^5$
$0 \le a_v,b_v \le 10^9$
$1 \le u_i,v_i \le n$
The graph is simple, connected, and undirected.
The sum of $n$ over all test cases is at most $2 \times 10^5$ .
The sum of $m$ over all test cases is at most $2 \times 10^5$ .

t

\left. \begin{array}{l} n \quad m \\ a_1 \quad a_2 \quad \ldots \quad a_n \\ b_1 \quad b_2 \quad \ldots \quad b_n \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array} \right\} \times t

\left. \begin{array}{l} \texttt{Yes} \;\text{or}\; \texttt{No} \end{array} \right\} \times t

The answer is case-insensitive. Any capitalization of the letters is accepted, including $\texttt{YES}$ , $\texttt{yes}$ , and $\texttt{YeS}$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

24D. One Ball Stays

Constraints

Input

Output

Samples

24D. One Ball Stays

Constraints

Input

Output

Samples