#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 open window children of root of /**each**/ tree in the forest
map < int , llu> r2;
map < int , llu> aux_map;
vi tree;
vector < bool > track;
vector < bool > vs;
bool dfs_fun( vvi & g, int x, vector < int > & key, vector < bool > & vs)
{
vs[ x] = true ;
bool res = false ;
for ( auto it : g[ x] )
if ( ! vs[ it] )
{
vs[ it] = true ;
if ( key[ it] == 1 )
{
res = true ;
break ;
}
else res = dfs_fun( g, it, key, vs) ;
}
return res;
}
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)
{
vs = vector< bool > ( 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( )
{
/*ios_base::sync_with_stdio(0);
cin.tie(0);*/
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 ;
}
tree.pb ( 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 ( ) + 1 ; //root of the very first tree
auto it2 = it1;
it2++ ; //root of the next tree
llu rubik = 0 ;
vector < tuple< int , int , int > > remaining;
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
rubik++ ;
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
rubik++ ;
else //else for the element must have at least two open window nodes rooted @ itself
remaining.pb ( make_tuple( x, * it1, * it2) ) ;
x++ ;
}
it1++ ; /*increment the tree*/
it2++ ;
} while ( * it1 ! = V+ 1 ) ;
/*cout<<"\ntuple is :\t";
for(auto it : remaining) cout<<get<0>(it)<<' '<<get<1>(it)<<' '<<get<2>(it)<<"\t";*/
for ( auto it : remaining)
{
vs = vector< bool > ( get< 2 > ( it) - get< 1 > ( it) , false ) ;
track = vector< bool > ( get< 2 > ( it) - get< 1 > ( it) , false ) ;
int i = 0 ;
while ( count( begin( track) , end( track) , true ) < 2 && i < g[ get< 0 > ( it) ] .size ( ) )
{
track[ i] = dfs_fun( g, get< 0 > ( it) , key, vs) ;
i++ ;
}
if ( count( begin( track) , end( track) , true ) >= 2 ) rubik++ ;
}
//cout<<"\nthe result of query 2 is :\t";
cout << rubik<< endl;
return 0 ;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBsbHUgbG9uZyBsb25nIHVuc2lnbmVkCiNkZWZpbmUgTUFYU0laRSAxMDAwMAojZGVmaW5lIHBiIHB1c2hfYmFjawp1c2luZyBuYW1lc3BhY2U6OnN0ZDsKCnR5cGVkZWYgdmVjdG9yIDxpbnQ+IHZpOwp0eXBlZGVmIHBhaXIgPCBpbnQsIGludCA+IGlpOwp0eXBlZGVmIHZlY3RvciA8IGlpID4gdmlpOwp0eXBlZGVmIHZlY3RvciA8dmlpPiB2dmlpOwp0eXBlZGVmIHZlY3RvciA8IHZpID4gdnZpOwoKLy9yMiBrZWVwcyB0cmFjayBvZiB0aGUgbm8uIG9mIG9wZW4gd2luZG93IGNoaWxkcmVuIG9mIHJvb3Qgb2YgLyoqZWFjaCoqLyB0cmVlIGluIHRoZSBmb3Jlc3QKbWFwIDxpbnQsIGxsdT4gcjI7Cm1hcCA8aW50LCBsbHU+IGF1eF9tYXA7CnZpIHRyZWU7CnZlY3RvciA8Ym9vbD4gdHJhY2s7CnZlY3RvciA8Ym9vbD4gdnM7Cgpib29sIGRmc19mdW4odnZpICZnLCBpbnQgeCwgdmVjdG9yIDxpbnQ+ICZrZXksIHZlY3RvciA8Ym9vbD4gJnZzKQp7CiAgICB2c1t4XSA9IHRydWU7CiAgICBib29sIHJlcyA9IGZhbHNlOwogICAgZm9yKGF1dG8gaXQgOiBnW3hdKQogICAgICAgIGlmKCF2c1tpdF0pCiAgICB7CiAgICAgICAgdnNbaXRdID0gdHJ1ZTsKICAgICAgICBpZihrZXlbaXRdID09IDEpCiAgICAgICAgewogICAgICAgICAgICByZXMgPSB0cnVlOwogICAgICAgICAgICBicmVhazsKICAgICAgICB9CiAgICAgICAgZWxzZSByZXMgPSBkZnNfZnVuKGcsIGl0LCBrZXksIHZzKTsKICAgIH0KICAgIHJldHVybiByZXM7Cn0KCmxsdSBkZnModnZpICZnLCB2ZWN0b3IgPGJvb2w+ICZ2cywgaW50IHYsIG1hcCA8aW50LCBsbHU+ICZyMiwgdmkgJmtleSkKewogICAgdnNbdl0gPSB0cnVlOwogICAgbGx1ICBjID0gMTsgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIC8vY29udHJpYnV0aW9uIG9mIHRoZSBub2RlIG9uIHdoaWNoIGRmcyBoYXMgYmVlbiBjYWxsZWQsIC4uLndlJ2xsIHJldHVybiBjLTEgbGF0ZXIgaWYgdGhpcyBub2RlcyB3aW5kb3cgaXMgY2xvc2VkCiAgICBmb3IoYXV0byBpdCA9IGdbdl0uYmVnaW4oKSA7IGl0ICE9IGdbdl0uZW5kKCkgOyArK2l0KQoKICAgICAgICAgICAgaWYoIXZzWyppdF0pCiAgICAgICAgYyArPSBkZnMoZywgdnMsICppdCwgcjIsIGtleSk7ICAgICAgICAgICAgICAgICAgICAgICAgICAvL2luY3JlbWVudCBjIGJ5IHRoZSBubyBvZiBvcGVuIHdpbmRvdyBub2RlcyByb290ZWQgYXQgYwoKCiAgICBpZihrZXlbdl0pICAgICAgewogICAgICAgICAgICAgICAgICAgIHIyW3ZdID0gYyA7ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLy9tYXAgcjIga2VlcHMgdHJhY2sgb2Ygbm8uIG9mIG9wZW4gd2luZG93IG5vZGVzIHJvb3RlZCBhdCBlYWNoIG5vZGUgb2YgdGhlIGdyYXBoCiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIGMgOwogICAgICAgICAgICAgICAgICAgIH0KICAgIHsKICAgICAgICByMlt2XSA9IGMtMSA7ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLy9pZiB0aGUgbm9kZSBoYXMgaXRzIHdpbmRvdyBjbG9zZWQsYWRqdXN0IGl0cyBjb250cmlidXRpb24gd2hpY2ggd2FzIGluaXRpYXRlZCBhcyAxCiAgICAgICAgcmV0dXJuIGMtMTsKICAgIH0KfQoKdm9pZCBkcm91Z2h0KHZ2aSAmZywgdmkgJmtleSwgaW50IFYsIHZpICZyMSkKewogICAgdnMgPSB2ZWN0b3I8Ym9vbD4gKFYrMSwgZmFsc2UpOwogICAgdnNbMF0gPSB0cnVlOwogICAgZm9yKGludCBpID0gMSA7IGkgPD0gViA7ICsraSkKICAgICAgICBpZighdnNbaV0pCiAgICB7CiAgICAgICAgdHJlZS5wYihpKTsgICAgICAgICAgICAgICAgICAgICAgICAgLy8gdGhlIHZlY3RvciB0cmVlIGtlZXBzIHRyYWNrIG9mIHJvb3Qgb2YgZWFjaCB0cmVlIGluIHRoZSBmb3Jlc3QKICAgICAgICByMS5wYihkZnMoZywgdnMsIGksIHIyLCBrZXkpKTsgICAgICAvL3RoZSB2ZWN0b3IgcjEgc3RvcmVzIHRoZSBubyBvZiAnb3BlbiB3aW5kb3cnIG5vZGVzIHJvb3RlZCBhdCBlYWNoIHJvb3Qgb2YgdGhlIGZvcmVzdCBpbmNsdWRpbmcgdGhlIHN0YXR1cyBvZiByb290CiAgICB9Cn0KCmxvbmcgbG9uZyB1bnNpZ25lZCBjYWxjdWxhdGUodmkgdHJlZSwgbWFwPGludCwgbGx1PiAmcjIpCnsKICAgIGxvbmcgbG9uZyB1bnNpZ25lZCBjb3VudCA9IDA7CiAgICBmb3IoYXV0byBpdCA9ICB0cmVlLmJlZ2luKCkgOyBpdCAhPSB0cmVlLmVuZCgpIDsgKytpdCkKICAgICAgICBjb3VudCArPSAocjJbKml0XSoocjJbKml0XS0xKSkvMjsKICAgIHJldHVybiBjb3VudDsKfQoKaW50IG1haW4oKQp7CiAgICAvKmlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7CiAgICBjaW4udGllKDApOyovCgogICAgaW50IFYsIEUsIHMsIGQsIHcsIHN0OwoKICAgIC8vY291dDw8IlxuZW50ZXIgdGhlIG5vIG9mIG5vZGVzIGFuZCBlZGdlcyA6XHQgIjsKICAgIGNpbj4+Vj4+RTsKCiAgICBmb3IoaW50IGkgPSAwIDsgaSA8PSBWIDsgKytpKQogICAgICAgIHsKICAgICAgICAgICAgcjJbaV0gPSAwOwogICAgICAgICAgICBhdXhfbWFwW2ldID0gMDsKICAgICAgICB9CgogICAgdHJlZS5wYigwKTsKICAgIHZpIHIxOwogICAgdmkga2V5KFYrMSk7CiAgICB2dmkgZyhWKzEpOwoKICAgICAvL2NvdXQ8PCJcbmVudGVyIHRoZSB3aW5kb3cgc3RhdHVzIFxuIjsKICAgIGtleVswXSA9IDA7CiAgICBmb3IoaW50IGkgPSAxIDsgIGkgPD0gViA7ICsraSkKICAgICAgICB7CiAgICAgICAgICAgIGNpbj4+c3Q7CiAgICAgICAgICAgIGtleVtpXSA9IHN0OwogICAgICAgIH0KCiAgICAvL2NvdXQ8PCJcbmVudGVyIGVhY2ggZWRnZVxuIjsKICAgIGZvcihpbnQgaSA9IDAgOyBpIDwgRSA7ICsraSkKICAgIHsKICAgICAgICBjaW4+PnM+PmQ7CiAgICAgICAgZ1tzXS5wYihkKTsKICAgICAgICBnW2RdLnBiKHMpOwogICAgfQoKICAgIGRyb3VnaHQoZywga2V5LCBWLCByMSk7CgogICAgIC8qY291dDw8Ilxubm8gb2Ygb3BlbiB3aW5kb3cgY2hpbGRyZW4gcm9vdGVkIEAgYSBwcnRpY3VsYXIgbm9kZShpbmNsdWRpbmcgaXRzIG93biBzdGF0dXMpIDogbm9kZSAtPiBvcGVuIHdpbmRvdyBjaGlsZHJlbiAiPDxlbmRsOwogICAgIGNvdXQ8PCJcbmlnb25yZSB0aGUgY2FzZSBmb3IgMCI8PGVuZGw7CiAgICAgZm9yKGF1dG8gaXQgOiByMikKICAgICAgICBjb3V0PDxpdC5maXJzdDw8IiAtPiAiPDxpdC5zZWNvbmQ8PGVuZGw7Ki8KCi8vICAgIGNvdXQ8PCJcbmFuc3dlciB0byBxdWVyeSAxIGlzIDogXHQiOwogICAgICAgY291dDw8Y2FsY3VsYXRlKHRyZWUsIHIyKTw8JyAnOwoKICAgICAgICB0cmVlLnBiKFYrMSk7ICAgICAgICAgICAgICAgICAgICAgIC8vIGxhc3QgZWxlbWVudCBvZiB0aGUgdmVjdG9yIHRyZWUgY29udGFpbnMgVisxIHRvIG1ha2UgdGhlIGRvIHdoaWxlIGxvb3AgKHRvIGZpbmQgYW5zd2VyIHRvIHF1ZXJ5IDIpYWhlYWQgZnVuY3Rpb25hbAogICAgICAgIGF1dG8gaXQxID0gdHJlZS5iZWdpbigpKzE7ICAgICAgICAgICAgLy9yb290IG9mIHRoZSB2ZXJ5IGZpcnN0IHRyZWUKICAgICAgICBhdXRvIGl0MiA9IGl0MTsKICAgICAgICBpdDIrKzsgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAvL3Jvb3Qgb2YgdGhlIG5leHQgdHJlZQogICAgICAgIGxsdSBydWJpayA9IDA7CiAgICAgICAgdmVjdG9yIDx0dXBsZTxpbnQsIGludCwgaW50PiA+IHJlbWFpbmluZzsKCiAgICAgICAgZG8gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLy9mb3Igcm9vdCBvZiBlYWNoIHRyZWUgaW4gdGhlIGZvcmVzdCBkbyB0aGUgZm9sbG93aW5nCiAgICAgICAgewogICAgICAgICAgICBsbHUgeCA9ICppdDEgOyAgICAgICAgICAgICAgICAgIC8vZmlyc3QgZWxlbWVudCBvZiB0aGUgcHJlc2VudCB0cmVlCiAgICAgICAgICAgIGxsdSByb290X2lkID0gcjJbeF07ICAgICAgICAgICAgLy9uby4gb2Ygb3BlbiB3aW5kb3cgbm9kZXMgcm9vdGVkIEAgbm9kZSB4CiAgICAgICAgICAgIHdoaWxlKCB4IDwgKml0MiApICAgICAgICAgICAgICAgLy9mb3IgZWFjaCBlbGVtZW50IG9mIHRoZSB0cmVlIHJvb3RlZCBhdCBpdDEgZG8gdGhlIGZvbGxvd2luZwogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpZihyMlt4XSA+IDAgJiYgcjJbeF0gPCByb290X2lkKSAgICAgICAgICAgIC8vZWxlbWVudCBoYXMgYXQgbGVhc3QgMSBvcGVuIHdpbmRvdyBjaGlsZCBhbHNvIHRoZXJlIGlzIHNvbWUgb3BlbiB3aW5kb3cgbm9kZSByb290ZWQgYXQgdGhlIHNhbWUgcm9vdCBhdCB3aGljaCB0aGUgZWxlbWVudCBpcyBoZW5jZSBhdCBsZWFzdCB0aGUgd2F5IGJldHdlZW4gdGhlc2UgMiBub2RlcyBjb25uZWN0cyAnZW0KICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJ1YmlrKys7CgogICAgICAgICAgICAgICAgICAgIGVsc2UgaWYoa2V5W3hdID09IDEgJiYgcjJbeF0gPiAxKSAgICAgICAvL2VsZW1lbnQgaGFzIGl0cyB3aW5kb3cgb3BlbiBhbmQgaGFzIGF0IGxlYXN0IG9uZSBvcGVuIHdpbmRvdyBjaGlsZCwgaGVuY2UgdGhlIHBhdGggYncgdGhlbSBjb25uZWN0cyAnZW0KICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJ1YmlrKys7CgogICAgICAgICAgICAgICAgICAgIGVsc2UgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLy9lbHNlIGZvciB0aGUgZWxlbWVudCBtdXN0IGhhdmUgYXQgbGVhc3QgdHdvIG9wZW4gd2luZG93IG5vZGVzIHJvb3RlZCBAIGl0c2VsZgogICAgICAgICAgICAgICAgICAgICAgICByZW1haW5pbmcucGIobWFrZV90dXBsZSh4LCAqaXQxLCAqaXQyKSk7CiAgICAgICAgICAgIHgrKzsKICAgICAgICAgICAgfQogICAgICAgICAgICBpdDErKzsgICAgICAgICAgICAgICAgICAvKmluY3JlbWVudCB0aGUgdHJlZSovCiAgICAgICAgICAgIGl0MisrOwoKICAgICAgICB9d2hpbGUoKml0MSAhPSBWKzEpOwogICAgICAgIC8qY291dDw8IlxudHVwbGUgaXMgOlx0IjsKICAgICAgICBmb3IoYXV0byBpdCA6IHJlbWFpbmluZykgICAgIGNvdXQ8PGdldDwwPihpdCk8PCcgJzw8Z2V0PDE+KGl0KTw8JyAnPDxnZXQ8Mj4oaXQpPDwiXHQiOyovCiAgICAgICAgZm9yKGF1dG8gaXQgOiByZW1haW5pbmcpCiAgICAgICAgewogICAgICAgICAgICB2cyA9IHZlY3Rvcjxib29sPiAoZ2V0PDI+KGl0KSAtIGdldDwxPihpdCksIGZhbHNlKTsKICAgICAgICAgICAgdHJhY2sgPSB2ZWN0b3I8Ym9vbD4gKGdldDwyPihpdCkgLSBnZXQ8MT4oaXQpLCBmYWxzZSk7CiAgICAgICAgICAgIGludCBpID0gMDsKICAgICAgICAgICAgd2hpbGUoY291bnQoYmVnaW4odHJhY2spLCBlbmQodHJhY2spLCB0cnVlKTwyICYmIGkgPCBnW2dldDwwPihpdCldLnNpemUoKSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICB0cmFja1tpXSA9IGRmc19mdW4oZywgZ2V0PDA+KGl0KSAsIGtleSwgdnMpOwogICAgICAgICAgICAgICAgICAgIGkrKzsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGlmKGNvdW50KGJlZ2luKHRyYWNrKSwgZW5kKHRyYWNrKSwgdHJ1ZSk+PTIpIHJ1YmlrKys7CiAgICAgICAgfQogICAgICAgIC8vY291dDw8IlxudGhlIHJlc3VsdCBvZiBxdWVyeSAyIGlzIDpcdCI7CiAgICAgICAgY291dDw8cnViaWs8PGVuZGw7CgogICAgICAgIHJldHVybiAwOwp9Cg==