All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Furik and Rubik have come to the sanatorium, which consists of N rooms and M passageways. Each passageway connects two rooms, and there is at most one way to move between each pair of rooms. Some rooms have opened windows. There is a draught between two different rooms if both rooms have opened windows, and are connected with each other by some way.
Furik is interested in one question: what is the number of pairs of rooms, which have a draught between them. Rubik wants to know what is the number of the rooms, which have at least one draught passing through the room.
The first line contains two space-separated integers N and M. The next line contains N integers, where the ith number is equal to 1, if the window in the room number i is opened, otherwise 0. Then the next M lines contain pairs of integers, where the ith pair denotes the numbers of the connected rooms by ith passageway. Consider that the rooms are numerated by different integers from 1 to N.
In a single line print two numbers, denoting the answers to Furik and Rubik questions.
- 1 ≤ N ≤ 50000 (5 × 104)
- 0 ≤ M ≤ N − 1
- There is at most one way to move between each pair of rooms, that is, the given graph is a forest
Input: 6 5 1 1 1 1 1 0 1 2 1 6 1 5 2 4 4 3 Output: 10 5 Input: 2 1 1 0 1 2 Output: 0 0
|Tags||easy, feb14, sereja|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.