CF1537F Figure Fixing

Description

You have a connected undirected graph made of $ n $ nodes and $ m $ edges. The $ i $ -th node has a value $ v_i $ and a target value $ t_i $ . In an operation, you can choose an edge $ (i, j) $ and add $ k $ to both $ v_i $ and $ v_j $ , where $ k $ can be any integer. In particular, $ k $ can be negative. Your task to determine if it is possible that by doing some finite number of operations (possibly zero), you can achieve for every node $ i $ , $ v_i = t_i $ .

Input Format

N/A

Output Format

N/A

Explanation/Hint

Here is a visualization of the first test case (the orange values denote the initial values and the blue ones the desired values): ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1537F/1a3ad14db7374ce21cd4060fc1b1fbe532afbff1.png)One possible order of operations to obtain the desired values for each node is the following: - Operation $ 1 $ : Add $ 2 $ to nodes $ 2 $ and $ 3 $ . - Operation $ 2 $ : Add $ -2 $ to nodes $ 1 $ and $ 4 $ . - Operation $ 3 $ : Add $ 6 $ to nodes $ 3 $ and $ 4 $ . Now we can see that in total we added $ -2 $ to node $ 1 $ , $ 2 $ to node $ 2 $ , $ 8 $ to node $ 3 $ and $ 4 $ to node $ 4 $ which brings each node exactly to it's desired value. For the graph from the second test case it's impossible to get the target values.