#include<bits/stdc++.h>
#define llu long long unsigned
#define MAXSIZE 10000
#define pb push_back
using namespace :: std ;
typedef vector < int > vi;
typedef pair < int , int > ii;
typedef vector < ii > vii;
typedef vector < vii> vvii;
typedef vector < vi > vvi;
//r2 keeps track of the no. of children of root of /**each**/ tree in the forest which are labeled 1
map < int , llu> r2;
map < int , llu> aux_map;
vi tree;
llu dfs( vvi & g, vector < bool > & vs, int v, map < int , llu> & r2, vi & key)
{
vs[ v] = true ;
llu c = 1 ; //contribution of the node on which dfs has been called, ...we'll return c-1 later if this nodes window is closed
for ( auto it = g[ v] .begin ( ) ; it ! = g[ v] .end ( ) ; ++ it)
if ( ! vs[ * it] )
c + = dfs( g, vs, * it, r2, key) ; //increment c by the no of open window nodes rooted at c
if ( key[ v] ) {
r2[ v] = c ; //map r2 keeps track of no. of open window nodes rooted at each node of the graph
return c ;
}
{
r2[ v] = c- 1 ; //if the node has its window closed,adjust its contribution which was initiated as 1
return c- 1 ;
}
}
void drought( vvi & g, vi & key, int V, vi & r1)
{
vector < bool > vs( V+ 1 , false ) ;
vs[ 0 ] = true ;
for ( int i = 1 ; i <= V ; ++ i)
if ( ! vs[ i] )
{
tree.pb ( i) ; // the vector tree keeps track of root of each tree in the forest
r1.pb ( dfs( g, vs, i, r2, key) ) ; //the vector r1 stores the no of 'open window' nodes rooted at each root of the forest including the status of root
}
}
long long unsigned calculate( vi tree, map< int , llu> & r2)
{
long long unsigned count = 0 ;
for ( auto it = tree.begin ( ) ; it ! = tree.end ( ) ; ++ it)
count + = ( r2[ * it] * ( r2[ * it] - 1 ) ) / 2 ;
return count;
}
int main( )
{
int V, E, s, d, w, st;
//cout<<"\nenter the no of nodes and edges :\t ";
cin >> V>> E;
for ( int i = 0 ; i <= V ; ++ i)
{
r2[ i] = 0 ;
aux_map[ i] = 0 ;
}
vi r1;
vi key( V+ 1 ) ;
vvi g( V+ 1 ) ;
//cout<<"\nenter the window status \n";
key[ 0 ] = 0 ;
for ( int i = 1 ; i <= V ; ++ i)
{
cin >> st;
key[ i] = st;
}
//cout<<"\nenter each edge\n";
for ( int i = 0 ; i < E ; ++ i)
{
cin >> s>> d;
g[ s] .pb ( d) ;
g[ d] .pb ( s) ;
}
drought( g, key, V, r1) ;
/*cout<<"\nno of open window children rooted @ a prticular node(including its own status) : node -> open window children "<<endl;
cout<<"\nigonre the case for 0"<<endl;
for(auto it : r2)
cout<<it.first<<" -> "<<it.second<<endl;*/
// cout<<"\nanswer to query 1 is : \t";
cout << calculate( tree, r2) << ' ' ;
tree.pb ( V+ 1 ) ; // last element of the vector tree contains V+1 to make the do while loop (to find answer to query 2)ahead functional
auto it1 = tree.begin ( ) ; //root of the very first tree
auto it2 = it1;
it2++ ; //root of the next tree
llu count = 0 ;
do //for root of each tree in the forest do the following
{
llu x = * it1 ; //first element of the present tree
llu root_id = r2[ x] ; //no. of open window nodes rooted @ node x
while ( x < * it2 ) //for each element of the tree rooted at it1 do the following
{
if ( r2[ x] > 0 && r2[ x] < root_id) //element has at least 1 open window child also there is some open window node rooted at the same root at which the element is hence at least the way between these 2 nodes connects 'em
count++ ;
else if ( key[ x] == 1 && r2[ x] > 1 ) //element has its window open and has at least one open window child, hence the path bw them connects 'em
count++ ;
else //else for the element must have at least two open window nodes rooted @ itself
{
vector < bool > vsz( x - * it1, true ) ; //mark all the nodes b4 x visited as we are interested to find the no. of open window nodes of subtree rooted @ x
for ( llu i = x ; i < * it2 ; ++ i) //mark all the remaining nodes(including itself) in the tree unvisited
vsz[ i] = false ;
if ( key[ x] ) //if the node has its window open calling dfs on it returns 1+no. of open window nodes rooted @ it
{
if ( dfs( g, vsz, x, aux_map, key) >= 3 )
count++ ;
}
else if ( dfs( g, vsz, x, aux_map, key) >= 2 ) //else if the node has its window closed calling dfs on it returns no. of open window nodes rooted @ it
count++ ;
}
x++ ;
}
it1++ ; /*increment the tree*/
it2++ ;
} while ( * it1 ! = V+ 1 ) ;
//cout<<"\nthe result of query 2 is :\t";
cout << count<< endl;
return 0 ;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBsbHUgbG9uZyBsb25nIHVuc2lnbmVkCiNkZWZpbmUgTUFYU0laRSAxMDAwMAojZGVmaW5lIHBiIHB1c2hfYmFjawp1c2luZyBuYW1lc3BhY2U6OnN0ZDsKCnR5cGVkZWYgdmVjdG9yIDxpbnQ+IHZpOwp0eXBlZGVmIHBhaXIgPCBpbnQsIGludCA+IGlpOwp0eXBlZGVmIHZlY3RvciA8IGlpID4gdmlpOwp0eXBlZGVmIHZlY3RvciA8dmlpPiB2dmlpOwp0eXBlZGVmIHZlY3RvciA8IHZpID4gdnZpOwoKLy9yMiBrZWVwcyB0cmFjayBvZiB0aGUgbm8uIG9mIGNoaWxkcmVuIG9mIHJvb3Qgb2YgLyoqZWFjaCoqLyB0cmVlIGluIHRoZSBmb3Jlc3Qgd2hpY2ggYXJlIGxhYmVsZWQgMQptYXAgPGludCwgbGx1PiByMjsKbWFwIDxpbnQsIGxsdT4gYXV4X21hcDsKdmkgdHJlZTsKCmxsdSBkZnModnZpICZnLCB2ZWN0b3IgPGJvb2w+ICZ2cywgaW50IHYsIG1hcCA8aW50LCBsbHU+ICZyMiwgdmkgJmtleSkKewogICAgdnNbdl0gPSB0cnVlOwogICAgbGx1ICBjID0gMTsgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIC8vY29udHJpYnV0aW9uIG9mIHRoZSBub2RlIG9uIHdoaWNoIGRmcyBoYXMgYmVlbiBjYWxsZWQsIC4uLndlJ2xsIHJldHVybiBjLTEgbGF0ZXIgaWYgdGhpcyBub2RlcyB3aW5kb3cgaXMgY2xvc2VkCiAgICBmb3IoYXV0byBpdCA9IGdbdl0uYmVnaW4oKSA7IGl0ICE9IGdbdl0uZW5kKCkgOyArK2l0KQoKICAgICAgICAgICAgaWYoIXZzWyppdF0pCiAgICAgICAgYyArPSBkZnMoZywgdnMsICppdCwgcjIsIGtleSk7ICAgICAgICAgICAgICAgICAgICAgICAgICAvL2luY3JlbWVudCBjIGJ5IHRoZSBubyBvZiBvcGVuIHdpbmRvdyBub2RlcyByb290ZWQgYXQgYwoKCiAgICBpZihrZXlbdl0pICAgICAgewogICAgICAgICAgICAgICAgICAgIHIyW3ZdID0gYyA7ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLy9tYXAgcjIga2VlcHMgdHJhY2sgb2Ygbm8uIG9mIG9wZW4gd2luZG93IG5vZGVzIHJvb3RlZCBhdCBlYWNoIG5vZGUgb2YgdGhlIGdyYXBoCiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIGMgOwogICAgICAgICAgICAgICAgICAgIH0KICAgIHsKICAgICAgICByMlt2XSA9IGMtMSA7ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLy9pZiB0aGUgbm9kZSBoYXMgaXRzIHdpbmRvdyBjbG9zZWQsYWRqdXN0IGl0cyBjb250cmlidXRpb24gd2hpY2ggd2FzIGluaXRpYXRlZCBhcyAxCiAgICAgICAgcmV0dXJuIGMtMTsKICAgIH0KfQoKdm9pZCBkcm91Z2h0KHZ2aSAmZywgdmkgJmtleSwgaW50IFYsIHZpICZyMSkKewogICAgdmVjdG9yIDxib29sPiB2cyhWKzEsIGZhbHNlKTsKICAgIHZzWzBdID0gdHJ1ZTsKCiAgICBmb3IoaW50IGkgPSAxIDsgaSA8PSBWIDsgKytpKQogICAgICAgIGlmKCF2c1tpXSkKICAgIHsKICAgICAgICB0cmVlLnBiKGkpOyAgICAgICAgICAgICAgICAgICAgICAgICAvLyB0aGUgdmVjdG9yIHRyZWUga2VlcHMgdHJhY2sgb2Ygcm9vdCBvZiBlYWNoIHRyZWUgaW4gdGhlIGZvcmVzdAogICAgICAgIHIxLnBiKGRmcyhnLCB2cywgaSwgcjIsIGtleSkpOyAgICAgIC8vdGhlIHZlY3RvciByMSBzdG9yZXMgdGhlIG5vIG9mICdvcGVuIHdpbmRvdycgbm9kZXMgcm9vdGVkIGF0IGVhY2ggcm9vdCBvZiB0aGUgZm9yZXN0IGluY2x1ZGluZyB0aGUgc3RhdHVzIG9mIHJvb3QKICAgIH0KfQoKbG9uZyBsb25nIHVuc2lnbmVkIGNhbGN1bGF0ZSh2aSB0cmVlLCBtYXA8aW50LCBsbHU+ICZyMikKewogICAgbG9uZyBsb25nIHVuc2lnbmVkIGNvdW50ID0gMDsKICAgIGZvcihhdXRvIGl0ID0gIHRyZWUuYmVnaW4oKSA7IGl0ICE9IHRyZWUuZW5kKCkgOyArK2l0KQogICAgICAgIGNvdW50ICs9IChyMlsqaXRdKihyMlsqaXRdLTEpKS8yOwogICAgcmV0dXJuIGNvdW50Owp9CmludCBtYWluKCkKewogICAgaW50IFYsIEUsIHMsIGQsIHcsIHN0OwoKICAgIC8vY291dDw8IlxuZW50ZXIgdGhlIG5vIG9mIG5vZGVzIGFuZCBlZGdlcyA6XHQgIjsKICAgIGNpbj4+Vj4+RTsKCiAgICBmb3IoaW50IGkgPSAwIDsgaSA8PSBWIDsgKytpKQogICAgICAgIHsKICAgICAgICAgICAgcjJbaV0gPSAwOwogICAgICAgICAgICBhdXhfbWFwW2ldID0gMDsKICAgICAgICB9CgogICAgdmkgcjE7CiAgICB2aSBrZXkoVisxKTsKICAgIHZ2aSBnKFYrMSk7CgogICAgIC8vY291dDw8IlxuZW50ZXIgdGhlIHdpbmRvdyBzdGF0dXMgXG4iOwogICAga2V5WzBdID0gMDsKICAgIGZvcihpbnQgaSA9IDEgOyAgaSA8PSBWIDsgKytpKQogICAgICAgIHsKICAgICAgICAgICAgY2luPj5zdDsKICAgICAgICAgICAga2V5W2ldID0gc3Q7CiAgICAgICAgfQoKICAgIC8vY291dDw8IlxuZW50ZXIgZWFjaCBlZGdlXG4iOwogICAgZm9yKGludCBpID0gMCA7IGkgPCBFIDsgKytpKQogICAgewogICAgICAgIGNpbj4+cz4+ZDsKICAgICAgICBnW3NdLnBiKGQpOwogICAgICAgIGdbZF0ucGIocyk7CiAgICB9CgogICAgZHJvdWdodChnLCBrZXksIFYsIHIxKTsKCiAgICAgLypjb3V0PDwiXG5ubyBvZiBvcGVuIHdpbmRvdyBjaGlsZHJlbiByb290ZWQgQCBhIHBydGljdWxhciBub2RlKGluY2x1ZGluZyBpdHMgb3duIHN0YXR1cykgOiBub2RlIC0+IG9wZW4gd2luZG93IGNoaWxkcmVuICI8PGVuZGw7CiAgICAgY291dDw8IlxuaWdvbnJlIHRoZSBjYXNlIGZvciAwIjw8ZW5kbDsKICAgICBmb3IoYXV0byBpdCA6IHIyKQogICAgICAgIGNvdXQ8PGl0LmZpcnN0PDwiIC0+ICI8PGl0LnNlY29uZDw8ZW5kbDsqLwoKICAgICAgIC8vIGNvdXQ8PCJcbmFuc3dlciB0byBxdWVyeSAxIGlzIDogXHQiOwogICAgICAgY291dDw8Y2FsY3VsYXRlKHRyZWUsIHIyKTw8JyAnOwoKICAgICAgICB0cmVlLnBiKFYrMSk7ICAgICAgICAgICAgICAgICAgICAgIC8vIGxhc3QgZWxlbWVudCBvZiB0aGUgdmVjdG9yIHRyZWUgY29udGFpbnMgVisxIHRvIG1ha2UgdGhlIGRvIHdoaWxlIGxvb3AgKHRvIGZpbmQgYW5zd2VyIHRvIHF1ZXJ5IDIpYWhlYWQgZnVuY3Rpb25hbAogICAgICAgIGF1dG8gaXQxID0gdHJlZS5iZWdpbigpOyAgICAgICAgICAgIC8vcm9vdCBvZiB0aGUgdmVyeSBmaXJzdCB0cmVlCiAgICAgICAgYXV0byBpdDIgPSBpdDE7CiAgICAgICAgaXQyKys7ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLy9yb290IG9mIHRoZSBuZXh0IHRyZWUKICAgICAgICBsbHUgY291bnQgPSAwOwoKICAgICAgICBkbyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAvL2ZvciByb290IG9mIGVhY2ggdHJlZSBpbiB0aGUgZm9yZXN0IGRvIHRoZSBmb2xsb3dpbmcKICAgICAgICB7CiAgICAgICAgICAgIGxsdSB4ID0gKml0MSA7ICAgICAgICAgICAgICAgICAgLy9maXJzdCBlbGVtZW50IG9mIHRoZSBwcmVzZW50IHRyZWUKICAgICAgICAgICAgbGx1IHJvb3RfaWQgPSByMlt4XTsgICAgICAgICAgICAvL25vLiBvZiBvcGVuIHdpbmRvdyBub2RlcyByb290ZWQgQCBub2RlIHgKICAgICAgICAgICAgd2hpbGUoIHggPCAqaXQyICkgICAgICAgICAgICAgICAvL2ZvciBlYWNoIGVsZW1lbnQgb2YgdGhlIHRyZWUgcm9vdGVkIGF0IGl0MSBkbyB0aGUgZm9sbG93aW5nCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGlmKHIyW3hdID4gMCAmJiByMlt4XSA8IHJvb3RfaWQpICAgICAgICAgICAgLy9lbGVtZW50IGhhcyBhdCBsZWFzdCAxIG9wZW4gd2luZG93IGNoaWxkIGFsc28gdGhlcmUgaXMgc29tZSBvcGVuIHdpbmRvdyBub2RlIHJvb3RlZCBhdCB0aGUgc2FtZSByb290IGF0IHdoaWNoIHRoZSBlbGVtZW50IGlzIGhlbmNlIGF0IGxlYXN0IHRoZSB3YXkgYmV0d2VlbiB0aGVzZSAyIG5vZGVzIGNvbm5lY3RzICdlbQogICAgICAgICAgICAgICAgICAgICAgICAgICAgY291bnQrKzsKCiAgICAgICAgICAgICAgICAgICAgZWxzZSBpZihrZXlbeF0gPT0gMSAmJiByMlt4XSA+IDEpICAgICAgIC8vZWxlbWVudCBoYXMgaXRzIHdpbmRvdyBvcGVuIGFuZCBoYXMgYXQgbGVhc3Qgb25lIG9wZW4gd2luZG93IGNoaWxkLCBoZW5jZSB0aGUgcGF0aCBidyB0aGVtIGNvbm5lY3RzICdlbQogICAgICAgICAgICAgICAgICAgICAgICAgICAgY291bnQrKzsKCiAgICAgICAgICAgICAgICAgICAgZWxzZSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAvL2Vsc2UgZm9yIHRoZSBlbGVtZW50IG11c3QgaGF2ZSBhdCBsZWFzdCB0d28gb3BlbiB3aW5kb3cgbm9kZXMgcm9vdGVkIEAgaXRzZWxmCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICB2ZWN0b3IgPGJvb2w+IHZzeih4IC0gKml0MSwgdHJ1ZSk7ICAgICAgLy9tYXJrIGFsbCB0aGUgbm9kZXMgYjQgeCB2aXNpdGVkIGFzIHdlIGFyZSBpbnRlcmVzdGVkIHRvIGZpbmQgdGhlIG5vLiBvZiBvcGVuIHdpbmRvdyBub2RlcyBvZiBzdWJ0cmVlIHJvb3RlZCBAIHgKICAgICAgICAgICAgICAgICAgICAgICAgZm9yKGxsdSBpID0geCA7IGkgPCAqaXQyIDsgKytpKSAgICAgICAgIC8vbWFyayBhbGwgdGhlIHJlbWFpbmluZyBub2RlcyhpbmNsdWRpbmcgaXRzZWxmKSBpbiB0aGUgdHJlZSB1bnZpc2l0ZWQKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHZzeltpXSA9IGZhbHNlOwogICAgICAgICAgICAgICAgICAgICAgICBpZihrZXlbeF0pICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLy9pZiB0aGUgbm9kZSBoYXMgaXRzIHdpbmRvdyBvcGVuIGNhbGxpbmcgZGZzIG9uIGl0IHJldHVybnMgMStuby4gb2Ygb3BlbiB3aW5kb3cgbm9kZXMgcm9vdGVkIEAgaXQKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYoZGZzKGcsIHZzeiwgeCwgYXV4X21hcCwga2V5KSA+PSAzKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgY291bnQrKzsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICBlbHNlIGlmKGRmcyhnLCB2c3osIHgsIGF1eF9tYXAsIGtleSkgPj0gMikgICAgICAgICAgLy9lbHNlIGlmIHRoZSBub2RlIGhhcyBpdHMgd2luZG93IGNsb3NlZCBjYWxsaW5nIGRmcyBvbiBpdCByZXR1cm5zIG5vLiBvZiBvcGVuIHdpbmRvdyBub2RlcyByb290ZWQgQCBpdAogICAgICAgICAgICAgICAgICAgICAgICAgICAgY291bnQrKzsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIHgrKzsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgaXQxKys7ICAgICAgICAgICAgICAgICAgLyppbmNyZW1lbnQgdGhlIHRyZWUqLwogICAgICAgICAgICBpdDIrKzsKCiAgICAgICAgfXdoaWxlKCppdDEgIT0gVisxKTsKICAgICAgICAvL2NvdXQ8PCJcbnRoZSByZXN1bHQgb2YgcXVlcnkgMiBpcyA6XHQiOwogICAgICAgIGNvdXQ8PGNvdW50PDxlbmRsOwoKICAgICAgICByZXR1cm4gMDsKfQo=