There are a total of n people in Prateek's class, numbered from 1 to n. Every person has…
- User
There are a total of n people in Prateek's class, numbered from 1 to n. Every person has some field of interest for their projects. There are a number people who have the same field of interest. Now, you are given a number of pairs of the form (x,y). This means that the students numbered x and y have interest in the same field. You task is to form groups, such that, all the people with the same field of interest are in the same group. No, member can be a member of more than one group. From each group, the proctor picks exactly two students and if the group has only one student, then, only one student is picked. These students will be responsible for submitting the progress report to the mentor. Calculate the number of ways in which these students can be picked. As the answer can be large, print it modulo 1000000007
NOTE: These pairs are transitive, and symmetric. INPUT The first line of input contains the number of test cases. Description of a test case is given below. 1.The first line of each test case contains two space separated integers n and k, the number of people and the number of pairs, respectively.
2.Then k lines follow, each containing 2 space separated integers x and y. This means that people numbered x and y have interest in the same field.
OUTPUT The output t lines, one for each test case. Each line contains the required answer for that test case.
CONSTRAINTS 1 ≤ t ≤ 5 1 ≤ n,k ≤ 100000 1 ≤ x,y ≤ n
SAMPLE INPUT 1 6 4 1 2 2 3 4 5 2 6
SAMPLE OUTPUT 6
Assistant
We need to parse problem: Given n people, and pairs (x,y) meaning they have same field of interest. The relation is transitive and symmetric, so effectively we have equivalence classes (connected components) representing groups of people sharing same field. However, note: pairs only indicate same field, but if there's no connection, they might still have same field? Actually typical interpretation: We have pairs indicating "same field", and the relation is equivalence, so groups are components. So we need to partition people into groups such that all people with same interest are in same group, and no one in multiple groups. That is essentially grouping by equivalence classes. So we have components sizes.
Now, from each group, the proctor picks exactly two students (if group size >=2) OR if group size =1, picks only one student. So from each component of size s, number of ways to choose the students: if s=1: only 1 way (choose that single student). if s>=2: choose exactly 2 from s, i.e., C(s,2). However careful: The description says: "From each group, the proctor picks exactly two students and if the group has only one student, then, only one student is picked." That suggests for groups size >=2, picks exactly two (i.e., combination of 2). For size=1, picks that one (only 1 way). So that's correct.
Now we need total number of ways to pick students across all groups? But careful: The problem states: "Calculate the number of ways in which these students can be picked." Usually, since picks are independent per group, total number of ways = product over groups of (ways to pick from that group). Because groups are distinct (they are separate fields) and picks are made from each group. So answer = ∏_{components} f(s_i) where f(1)=1, f(s)=C(s,2) for s>=2.
But sample: n=6, pairs: (1,2),(2,3),(4,5),(2,6). Let's compute components: edges: 1-2-3, also 2-6 => actually graph: 1-2-3-? plus 2-6, so nodes: 1,2,3,6 all connected. So component1: {1,2,3,6} size=4. Component2: {4,5} size=2. There is no node left? n=6, we have covered all? 1,2,3,4,5,6 -> yes. So groups: size4 and size2. f(4)=C(4,2)=6, f(2)=C(2,2)=1. Product=6*1=6. That matches sample output 6. So product.
Hence problem reduces to: For each test case, given n and k pairs (x,y), compute connected components sizes (via union-find / DSU), then compute product modulo 1e9+7 of C(size,2) for each component with size>=2, and for size 1, multiply by 1 (i.e., ignore). But careful: If a component size is 1, C(1,2)=0? But we define f(1)=1, so effectively we can treat product over all components of (size choose 2) if size>=2, else 1. Or simply compute product of max(1, C(size,2)). Equivalent.
Alternatively, we can compute product of (size*(size-1)/2 mod M) for sizes>=2, else 1.
Edge Cases: There might be isolated nodes (no pairs) => component size=1, contribute 1. So product doesn't change.
Constraints: t up to 5, n,k up to 100000 each. So total across test cases? Not specified, but per test case we can handle O(n α(n) + k). So DSU.
Implementation: For each test case:
- Read n, k.
- Initialize DSU of size n+1 (1-indexed).
- For i in 1..k: read x,y, union(x,y).
- After unions, count sizes: for each node from 1..n, find root, increment count[root].
- Then iterate over roots with count>0, for each component size s: if s>1: ans = ans * (s*(s-1)//2 % MOD) % MOD. For s==1 do nothing.
- Print ans.
But careful: multiplication modulo MOD; use mod operations. Since s up to n (1e5), s*(s-1)/2 may be up to ~5e9, which fits in 64-bit but we compute modulo. Use (s % MOD)((s-1) % MOD) * inv2 % MOD? But since we need integer exact division by 2 before modulo? Since s and s-1 one is even, we can compute (s(s-1)//2) % MOD as ((s % MOD)((s-1) % MOD) % MOD * inv2) % MOD, where inv2 = (MOD+1)//2 because MOD is prime (1e9+7). Alternatively, compute using integer division then mod. But s(s-1) may be up to 10^10, fits in Python int. Python handles big ints, so we can compute (s*(s-1)//2) % MOD directly. So simpler.
But for large n (like 10^5) product of many components could be huge, but we mod.
Potential pitfalls: When there is no group? All isolated => product over 1's =1. So answer 1. Should be fine.
Now is there any nuance? The problem statement: "These pairs are transitive, and symmetric." So indeed equivalence. Also note: The groups are formed such that all people with same field of interest are in same group. That is exactly components. So answer is product.
But wait, could there be a scenario where some people share same field but not directly or indirectly connected through given pairs? Since the pairs are only given, the relation is defined as the equivalence closure of those pairs. So if there is no pair linking two persons, they may or may not have same interest? But the problem says: "There are a number people who have the same field of interest. Now, you are given a number of pairs of the form (x,y). This means that the students numbered x and y have interest in the same field." It doesn't say that these are the only pairs; it's just given information. But the relation is transitive, so if we have pairs (1,2) and (2,3), then 1,2,3 all same interest. So indeed we can infer groups. And if there is no connection, we cannot assume they have same interest; they could have different interests. So grouping must respect that people with same interest must be in same group, but people with different interests must be in different groups. However we are not given any negative information. The task: "form groups, such that, all the people with the same field of interest are in the same group." So we must partition into groups consistent with the equivalence closure. The minimal grouping that satisfies is each equivalence class as a separate group. But could we merge two components? That would put people who are not known to share same interest in same group. But the requirement is only that people with same interest are together; it doesn't say that people with different interests cannot be together? Actually the phrasing: "such that, all the people with the same field of interest are in the same group. No member can be a member of more than one group." It doesn't explicitly forbid grouping people with different interests together. However typically such problems imply that we partition into groups that exactly correspond to fields. Usually we interpret that the groups are formed based on the given information: we need to put those who share interest together, and we don't have to separate those who might have different interests? But if we merge two components that have no known common interest, then we would be putting potentially different-interest people together. Does the problem allow that? It says: "form groups, such that, all the people with the same field of interest are in the same group." That is a condition: if two people have the same field, they must be in same group. It does NOT say that if they have different fields they must be in different groups. So theoretically we could merge components as long as we don't split any component. However, there is also constraint: "No, member can be a member of more than one group." So groups are disjoint. So we could create groups that are unions of multiple components. But is there any further constraint? Possibly the goal is to minimize number of groups? Or the problem implies that the groups are determined by the equivalence classes (fields) exactly. Let's examine sample: n=6, components: size4 and size2. If we could merge them into one group of size6, then from that group we would pick exactly two students? Wait but from each group we pick either 2 or 1 if group size=1. But if we merge two components, group size would be >=2, we would pick exactly two students total from that merged group. However the problem says "From each group, the proctor picks exactly two students and if the group has only one student, then, only one student is picked. These students will be responsible for submitting the progress report to the mentor." That suggests that each group yields some students to submit progress reports. If we merge components, we would be picking only 2 students from a larger group, whereas originally we would pick 2 from each group (if size>=2). That would change total count of picked students. But the question: "Calculate the number of ways in which these students can be picked." It seems that grouping is part of the process? Or is grouping predetermined by the fields? Let's read carefully.
Problem statement:
"There are a total of n people in Prateek's class, numbered from 1 to n. Every person has some field of interest for their projects. There are a number people who have the same field of interest. Now, you are given a number of pairs of the form (x,y). This means that the students numbered x and y have interest in the same field. You task is to form groups, such that, all the people with the same field of interest are in the same group. No, member can be a member of more than one group. From each group, the proctor picks exactly two students and if the group has only one student, then, only one student is picked. These students will be responsible for submitting the progress report to the mentor. Calculate the number of ways in which these students can be picked. As the answer can be large, print it modulo 1000000007
NOTE: These pairs are transitive, and symmetric."
Interpretation: "You task is to form groups, such that, all the people with the same field of interest are in the same group." So we are to decide grouping, subject to constraints: if they have same field, they must be in same group. However, we could put people with different fields into same group? Possibly not prohibited, but then they would be in the same group despite having different fields; is that allowed? It might violate the condition that groups correspond to fields? Actually "such that, all the people with the same field of interest are in the same group" doesn't say that groups must contain only people with same field. It only says that for any two people with same field, they must be grouped together. It does not say that groups cannot contain people with different fields. So mathematically, we can partition the set into groups that are unions of equivalence classes (components) of the "same field" relation. Since the relation is an equivalence relation (transitive closure of given pairs), the equivalence classes are the maximal sets where everyone is known to have same field. If we combine multiple equivalence classes into one group, we still satisfy that same-field people are together because each class is wholly contained. But then a group would contain multiple fields. Is that allowed? Possibly yes. However, then the proctor picks students from each group. The number of ways to pick students depends on group sizes. So we could potentially choose a grouping to maximize or minimize the number of ways? But the problem asks: "Calculate the number of ways in which these students can be picked." That suggests grouping is fixed by some rule, not arbitrary. Usually in such problems, the groups are exactly the connected components (i.e., the fields). Because the pairs indicate who shares the same field, and we assume that if there is no connection, they have different fields. So the natural grouping is the equivalence classes. The phrase "You task is to form groups, such that, all the people with the same field of interest are in the same group." could be interpreted as: given the pairs, you need to partition into groups that satisfy that condition. Among all possible partitions that satisfy the condition, perhaps we need to consider the number of ways to pick students? But then the grouping itself is variable; the number of ways to pick students would depend on the grouping chosen. So there would be many possible pickings, but we might need to count the number of ways across all possible groupings? That seems complex.
Let's read again: "You task is to form groups, such that, all the people with the same field of interest are in the same group. No, member can be a member of more than one group. From each group, the proctor picks exactly two students and if the group has only one student, then, only one student is picked. These students will be responsible for submitting the progress report to the mentor. Calculate the number of ways in which these students can be picked." The phrasing might be ambiguous: Perhaps the groups are predetermined by the condition (i.e., we must put each equivalence class into one group). The sentence "You task is to form groups, such that, all the people with the same field of interest are in the same group." might be describing what we need to do: i.e., we need to find the grouping that respects the given same-field relations. It's not optional; we must do that. And then after grouping, picks happen. So the grouping is uniquely determined (the equivalence classes) because any other grouping that merges classes would still satisfy the condition, but maybe the intention is to put each distinct field into a separate group. The phrase "all the people with the same field of interest are in the same group" does not forbid merging fields, but it's typical to interpret that each group corresponds to a distinct field. Additionally, the note "These pairs are transitive, and symmetric." suggests that the relation is equivalence, thus the "fields" partition the set. Usually in such problems (like "friendship groups", "components"), the answer is product of C(s_i,2). Also sample matches.
Therefore we go with standard interpretation: groups = connected components.
But let's double-check via possible alternative: Suppose we have two components (size a and b). If we combine them into one group of size a+b, the number of ways to pick students from that group would be C(a+b, 2). The total ways for the combined grouping would be just that, because there's only one group. For the separate grouping, product = C(a,2)C(b,2) (or possibly 1 if b=1 etc). These are different. Which one does sample produce? For sample a=4,b=2: product =61=6; combined group: C(6,2)=15. But output is 6. So not combined. So grouping must be the component-wise grouping.
Hence answer = product over components of C(size,2) for size>=2, and 1 for size=1.
So solution: DSU to get component sizes, then product.
Implementation details: DSU with path compression and union by size/rank. Since n up to 1e5, easy.
But there may be multiple test cases, sum of n across test cases maybe up to 5e5? But constraints per test case, t up to 5, each up to 1e5, so total up to 5e5, which is fine.
Edge Cases: large component size up to 1e5, C(1e5,2)= ~5e9, mod safe.
Now modulo: MOD = 1000000007 (1e9+7). We'll compute ans = 1 initially, for each size s>1: ans = (ans * (s*(s-1)//2)) % MOD.
Potential overflow in intermediate multiplication? Python big ints fine.
But careful: For large n, product of many components could be large, but mod each step.
Time Complexity: O(n + k α(n)).
Now we need to output answer for each test case.
Implementation plan:
def solve(): import sys input = sys.stdin.readline MOD = 1000000007 t = int(input().strip()) for _ in range(t): line = '' while line.strip()=='': line = input() n,k = map(int,line.split()) parent = list(range(n+1)) size = [1](n+1) def find(x): while parent[x]!=x: parent[x] = parent[parent[x]] x = parent[x] return x def union(x,y): rx = find(x) ry = find(y) if rx == ry: return if size[rx] < size[ry]: rx,ry = ry,rx parent[ry] = rx size[rx] += size[ry] for i in range(k): x,y = map(int,input().split()) union(x,y) # Count component sizes (or we can directly use size array after unions but need root sizes) # We'll build a dict or array for root counts # We can iterate i from 1 to n, find root, and increment count in a dict. # But we can also use size array only for roots after unions? However after path compression, some nodes may not have updated size. But we have size array storing tree sizes at roots. After unions, we can find each node's root and then we can collect root sizes using a set. roots = set() for i in range(1,n+1): r = find(i) roots.add(r) ans = 1 for r in roots: s = size[r] # because size[r] holds the component size if r is root (we maintained it) if s > 1: ways = (s(s-1)//2) % MOD ans = (ans * ways) % MOD print(ans)
But note: After path compression, the size array for non-root nodes is not accurate (they still hold old size from when they were root maybe). But we only use size[r] for roots. Since we call find(i) for all i, that compresses and ensures parent pointers updated, but size of root remains correct. So size[r] for root r is correct. So we can use that.
Alternatively, we could use a separate counter dict: count[root] +=1 and then compute s. But using size is simpler.
Make sure to initialize parent and size correctly.
Potential issue: For large n (1e5) and many find calls, recursion depth? We'll implement iterative find or recursive with sys.setrecursionlimit? Python recursion limit may be okay if depth is small due to path compression, but safer to use iterative.
We'll implement find iteratively.
Testing with sample.
Now any more nuance? Possibly there are multiple edges or self-loops? Not mentioned, but x and y are distinct? Not specified, but likely x != y? Could be same? Typically pairs are between distinct persons. But even if x==y, it doesn't affect union.
If k=0, then each person is separate component of size 1, product = 1. So output 1.
Now confirm with sample.
We'll test with sample.
We'll simulate: n=6,k=4. DSU: unions as described. roots: after all, root for 1 might be 2? But size at root correct. size[some root] = 4, other =2. ans =6. Good.
Now complexity wise, O(t*(n+k)).
We need to ensure we handle multiple test cases and reset structures each case.
Now note: Input may have extra spaces, we can use standard reading.
Potential memory: parent array of size n+1 each test case, okay.
Now check for large: 1e5, find operations per node and per union (each union does two finds). So total ~ n + 2k finds, fine.
Thus answer.
But wait: There is a nuance: The problem says "From each group, the proctor picks exactly two students and if the group has only one student, then, only one student is picked." This is exactly as we used. However, could it be that if group size is 0? No groups always contain at least one student because each person belongs to exactly one group. So fine.
One more thought: The sample output 6 matches product.
Hence solution is straightforward.
Now let's produce final answer.
But before finalizing, consider if there is any other interpretation that could yield different answer, but given sample, product is correct.
Hence we will code.
We'll write solve() and if name == "main": solve().
Now careful about reading input: There may be blank lines? Possibly not, but we can use input().strip().
Simpler:
for _ in range(t): n,k = map(int,input().split()) parent = list(range(n+1)) size = [1]*(n+1) # define functions for i in range(k): x,y = map(int,input().split()) union(x,y) # after unions, we can compute component sizes using a dict from root to count. # Actually we could also get unique roots by checking parent[i]==i? But after path compression, parent[i] might be root for all i, so we can just iterate and if parent[i]==i: s=size[i] else... but find ensures compression, but we need to call find to get root. So simpler: for i in 1..n: r=find(i); if i==r? Not necessarily because after find(i) we compress but the root may not be stored in parent[i]? Actually find(i) returns root and also sets parent[i]=root. So after loop, parent[i] holds root. So we can iterate and use parent[i] directly? But careful: after find(i), parent[i] is set to root. So after all finds, for each i, parent[i] is root. So we can then count: count[parent[i]]++. But we can also just compute ans from size of roots after we have found them all. Using set of roots and size from the maintained size array.
We'll do:
roots = set() for i in range(1,n+1): r = find(i) roots.add(r) ans=1 for r in roots: s = size[r] if s>1: ans = ans * (s*(s-1)//2) % MOD print(ans)
Alternatively, we can create an array comp_size = [0]*(n+1) and for each i: root=find(i); comp_size[root] +=1; then use comp_size. That avoids reliance on size array which might be inaccurate for nodes that became non-root after union? But we maintain size for roots correctly. In union we update size[rx] += size[ry], and we don't modify size[ry] after that. So size[ry] still holds old size but ry is no longer root. When we later call find(ry) or any node under ry, the root will be rx. So size[ry] is obsolete. So using size[r] for roots only is fine. But if we iterate roots from set, each is a root, so size[r] is correct. So fine.
We must ensure that after all unions, we call find on all nodes to compress paths, so that parent[i] is root, and we can identify roots: root = parent[i] for each i, but after compression, each parent[i] is root; so we could also check if parent[i]==i? Actually after compression, parent[i] is root. For nodes that are roots, parent[i]==i. So we could simply loop and if parent[i]==i: then it's a root. However, if we haven't called find on all nodes, some non-root nodes might still have parent that is not root (i.e., not fully compressed). But we can call find on all nodes to compress. So after that, parent[i]==i only for roots. So we can identify roots that way. So:
for i in range(1,n+1): find(i) Then: for i in range(1,n+1): if parent[i]==i: s = size[i] # size stored at root if s>1: ans = ans * (s*(s-1)//2) % MOD
That works and avoids set.
We'll adopt that.
Now note: In union we might update size of root, but we don't compress paths of all nodes. So after unions, we must compress. So we can do:
for i in range(1,n+1): find(i)
But find(i) already compresses and returns root. So we can just do it.
Implementation details: define find recursively? iterative fine.
We'll write:
def find(x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x
Now union:
def union(a,b): ra = find(a) rb = find(b) if ra == rb: return if size[ra] < size[rb]: ra, rb = rb, ra parent[rb] = ra size[ra] += size[rb]
Now code.
We'll include modulo constant.
Edge Cases: The product might be zero? No, C(s,2) is nonzero for s>=2, product of positive ints mod mod.
Now let's test with some custom:
Case1: t=1, n=1,k=0 => output 1. Case2: n=2,k=1 (1 2) => components: size2 => C(2,2)=1 => output 1. Case3: n=3, pairs: (1,2) => components: size2 and size1 => product = C(2,2)*1=1. Case4: n=3, pairs: (1,2),(2,3) => component size3 => C(3,2)=3 => output 3. Case5: n=4, no pairs => 1. Case6: n=4, pairs: (1,2),(3,4) => product = C(2,2)C(2,2)=11=1. Case7: n=5, pairs: (1,2),(2,3),(4,5) => product = C(3,2)C(2,2)=31=3.
Seems plausible.
Now we can produce final solution.
But wait: Could there be multiple test cases with large total n, and we need to ensure we don't exceed memory? We'll allocate fresh arrays per test case.
Now one more nuance: The pairs are transitive and symmetric. So they effectively define equivalence. So the solution stands.
Now I'll write final code.
Also note: The input format: first line t, then for each test case, first line n and k, then k lines. There might be extra whitespace, but we can use strip.
We'll implement.
Time complexity: O((n+k) α(n)) per test case.
Now produce final answer.
But before finalizing, I'd like to double-check if there is any hidden nuance: Possibly the number of ways to pick students includes the assignment of which group the student is in? But groups are fixed. Or maybe the students picked are "responsible for submitting the progress report to the mentor", and there might be some ordering? But likely not. So the answer is product.
Thus final answer.
Now write solution in Python.
We'll use sys.stdin.read for speed? Not necessary but okay. We'll use sys.stdin.readline.
Now code:
import sys
def solve(): import sys input = sys.stdin.readline MOD = 1000000007 t = int(input().strip()) for _ in range(t): # There might be blank lines, skip line = input() while line.strip() == '': line = input() n, k = map(int, line.split()) parent = list(range(n+1)) size = [1](n+1) def find(x): # iterative with path compression while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x def union(a,b): ra = find(a) rb = find(b) if ra == rb: return if size[ra] < size[rb]: ra, rb = rb, ra parent[rb] = ra size[ra] += size[rb] for i in range(k): a,b = map(int,input().split()) union(a,b) # compress all for i in range(1,n+1): find(i) ans = 1 for i in range(1,n+1): if parent[i] == i: s = size[i] if s > 1: ways = (s(s-1)//2) % MOD ans = (ans * ways) % MOD print(ans)
if name == "main": solve()
That should work.
But we need to be careful: In some DSU implementations, after union, size[rb] is not updated to 0 or something, but we only use size for roots, and we compress all so parent[i]==i only for roots. That works.
Now, is there any possibility of overflow in s*(s-1)//2? Python big ints safe.
Now check with sample:
Input: 1 6 4 1 2 2 3 4 5 2 6
Our code: parent and size after unions: likely root for 1,2,3,6 is same (e.g., 2) with size 4; root for 4,5 is e.g., 4 with size 2; after compress all, parent[2]==2? Actually after union: we union 1,2: size[1] or [2]? Let's simulate: initial parent each self, size1. union(1,2): ra=1, rb=2, size[1]==size[2]? both 1, if we compare, if size[ra] < size[rb]? 1<1 false, so ra=1, rb=2, parent[2]=1, size[1]=2. union(2,3): find(2) => after path compression? 2's parent is 1, so ra=find(2)=1, find(3)=3, size[1]=2, size[3]=1, ra=1, rb=3, parent[3]=1, size[1]=3. union(4,5): similar, size[4]=2. union(2,6): find(2)=1, find(6)=6, parent[6]=1, size[1]=4. After compress: loop i=1..6: find(1)=1, find(2) compress to 1, find(3) compress to 1, find(4)=4? Actually find(4)=4 because not merged, find(5) compress to 4, find(6) compress to 1. So parent[1]=1, parent[2]=1, parent[3]=1, parent[4]=4, parent[5]=4, parent[6]=1. So roots: i=1 and i=4. size[1]=4, size[4]=2. ans= C(4,2)=6, times C(2,2)=1 => 6. Good.
Now edge: n=1, k=0. After compress: root i=1, size[1]=1, s>1? false, ans remains 1. Output 1.
All good.
Now consider t up to 5, each n up to 100000, each k up to 100000, so total operations ~ 1e6, fine.
We'll finalize.
Potential improvements: Use sys.setrecursionlimit for recursive find, but we used iterative.
Now final answer.
But wait: Problem statement might have trap: "No, member can be a member of more than one group." Possibly a typo: "No member can be a member of more than one group." So groups partition.
All consistent.
Thus answer.
Now produce final response.
But is there any need to consider modulo division by 2? We used integer division before mod, which is fine because s*(s-1)//2 yields integer. However for large s, s*(s-1) might be up to 10^10, still fine.
Now maybe they want to compute product of C(s,2) mod MOD. Could there be any case where s is large enough that s*(s-1) overflows in languages like C++, but we are Python.
Now final code.
We'll present the solution in a clear way, with explanation in comments.
Now the final answer includes code.
But the instruction: "You are ChatGPT ... Provide the final answer." We should output the code.
Given that the problem is from coding platform, we likely need to provide the solution in Python.
Thus final. ```python
import sys
MOD = 1000000007
def solve() -> None: input = sys.stdin.readline t = int(input().strip()) for _ in range(t): # skip possible empty lines line = input() while line.strip() == '': line = input() n, k = map(int, line.split())
parent = list(range(n + 1)) size = [1] * (n + 1) # iterative find with path compression def find(x: int) -> int: while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x # union by size def union(a: int, b: int) -> None: ra = find(a) rb = find(b) if ra == rb: return if size[ra] < size[rb]: ra, rb = rb, ra parent[rb] = ra size[ra] += size[rb] # process all given pairs for _ in range(k): x, y = map(int, input().split()) union(x, y) # compress all paths to ensure parent[i] == i only for roots for i in range(1, n + 1): find(i) ans = 1 for i in range(1, n + 1): if parent[i] == i: # i is a root -> a component s = size[i] if s > 1: ways = (s * (s - 1) // 2) % MOD ans = (ans * ways) % MOD print(ans)if name == "main": solve()