1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
vector<int> A[200001];
vector<bool> NOWY(200001);
int tab[200001];
queue<int> k;
int bfs(int w){
int wyn = 0;		
 queue<int> kolejka;
 kolejka.push(w); //wstawiamy pierwszy wierzcholek do kolejki
 NOWY[w]=false; //oznaczamy go jako odwiedzony
 //cout<<w<<" ";
 while(!kolejka.empty()){ //dopoki kolejka nie jest pusta
    int v=kolejka.front(); // wez pierwszy wierzcholek v z kolejki
    kolejka.pop();  // usun go z kolejki
    for(int j=0;j<A[v].size();j++) {
        int s =  A[v][j];  //s - sasiad v     
        if(NOWY[s]==true) {
            wyn++;	
            //cout<<s<<" ";//wypisz go (tak sobie)
            kolejka.push(s); // dodaj go do kolejki
            NOWY[s]=false; // i oznacz jako odwiedzony
            }
        }                    
    }
    return wyn;
 }
void wypisz_graf(int n);
 
int main()
{
	ios_base::sync_with_stdio(0); cin.tie();cout.tie();
	int n, m, i, j, w1, w2, r = 1000000007;
	long long skladowa = 0, wyn = 1;
	cin >> n >> m;
	for(int i=1;i<=n;i++) cin >> tab[i];
	for(int i=0;i<m;i++) {
        cin>>w1>>w2; 
        A[w1].push_back(w2);
        A[w2].push_back(w1);
        if (tab[w1] == tab[w2]){
            k.push(w1); 
 			k.push(w2);  
		}
    }
                     
	//wypisz_graf(n);
	for(int i=0;i<=n;i++) NOWY[i]=true; 
	while(!k.empty()){ 
		w1 = k.front(); k.pop();
		if (NOWY[w1] == true) skladowa = bfs(w1);
		wyn *= skladowa % r;
    }
    cout << wyn << endl;
    return 0;
}
void wypisz_graf(int n)
{
   for(int i=1; i<=n ; i++)//dla kazdego wierzcholka i
   {
           cout<<i<<": "; //wypisz wierzcholek
           for(int j=0;j<A[i].size(); ++j) cout<< A[i][j]<<" "; //wypisz kazdego sasiada z listy sasiedztwa
           cout<<endl; 
           }        
}