Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Help to Be Happy

By AbuBokor · Limits 1s, 512 MB

A country named Mueawin has one or more villages and one or more people live in every village. Two people live in the same village if they are connected i.e. if it is possible to go from one’s home to others.
In this country, a man called happy if he/she has h or more units of money. EID is coming soon so everyone wants to be happy on EID-Day. If a man has x units of money, then he can give at most 10% of (x - h) units of money to his villagers only if x > h.
Note: a man can give money to others if they live in the same village.
By sharing money, is it possible to make happy all of a village ?
A village is called happy if all of its villagers are happy otherwise the village is not happy.

The king of this country wants to know how many villages in his country and how many happy and not happy village in his country. He also wants to know in what kind of village the ith people live. Can you inform the king?

Note that, Here we are just dealing with the integer part of the value, 10% of any amount.
For example, 10% of 365 is:
=> 365 × 10%
=> 365 × 10100
=> 36.5
The integer part of 36.5 is 36. So the 10% of 365 = 36.

Input

The first line of the input contains two positive integers n (1 ≤ n ≤ 105) and m (1 ≤ q ≤ 2 × 105) — The number of people in the country and the number of relations between each other.
The next line contains n positive integers am1, am2, am3amn, the initial amount of the n people where ami (1 ≤ ami ≤ 106) is the initial amount of the ith person.
The next line also contains n positive integers h1, h2, h3hn, where hi (1 ≤ hi ≤ 106) is the minimum amount to become the ith person happy.
Each of the next m lines will contain two positive integers u and v (1 ≤ u, v ≤ n, u != v), which means two people numbered with u and v are connected with each other.

Output

Print the total number of village, the number of happy village and the number of not happy village separating by space. In the next line print n integers with values 0 or 1. If ith people live in the happy village then print 1 otherwise print 0.

Samples

InputOutput
5 3
1200 1300 14000 30000 2900
3000 3000 3000 3000 3000
1 3
2 4
3 4
2 1 1
1 1 1 1 0

The configuration of the country.

InputOutput
3 3
1 2 3
2 3 1
1 2
2 3
3 1
1 0 1
0 0 0

Discussion

Statistics


92% Solution Ratio

jisan047Earliest, 1M ago

jisan047Fastest, 0.0s

naimulhasanLightest, 1.7 MB

mijanurShortest, 1076B

Submit

Login to submit